Please wait a minute...
Computational Visual Media  2020, Vol. 6 Issue (4): 431-443    doi: 10.1007/s41095-020-0192-6
Research Article     
Simple primitive recognition via hierarchical face clustering
Xiaolong Yang1,2(),Xiaohong Jia1,2,(✉)()
1 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
2 University of Chinese Academy of Sciences, Beijing 100049, China
Download: PDF (1009 KB)      HTML  
Export: BibTeX | EndNote (RIS)      

Abstract  

We present a simple yet efficient algorithmfor recognizing simple quadric primitives (plane, sphere, cylinder, cone) from triangular meshes. Our approach is an improved version of a previous hierarchical clustering algorithm, which performs pairwise clustering of trianglepatches from bottom to top. The key contributions of our approach include a strategy for priority and fidelity consideration of the detected primitives, and a scheme for boundary smoothness between adjacent clusters. Experimental results demonstrate that the proposed method produces qualitatively and quantitatively better results than representative state-of-the-art methods on a wide range of test data.



Key wordsquadric primitive extraction      mesh      hierar-chical clustering     
Received: 29 April 2020      Published: 30 November 2020
Fund:  National Natural Science of Foundation for Outstanding Young Scholars(12022117);National Natural Science Foundation of China(61872354);Beijing Natural Science Foundation(Z190004);Intelligent Science and Technology Advanced subject project of University of Chinese Academy of Sciences(115200S001)
Corresponding Authors: Xiaohong Jia     E-mail: yangxiaolong17@mails.ucas.ac.cn;xhjia@amss.ac.cn
About author: Xiaolong Yang received his B.S. degree in information and computing science from Northwestern Polytechnical University in 2017 and is currently pursuing his M.S. and Ph.D. degrees at the Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences. His research interests are in computer graphics and computer vision.|Xiaohong Jia is an associate professor at the Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences. She received her Ph.D. and bachelor degrees from the University of Science and Technology of China in 2009 and 2004, respectively. Her research interests include computer graphics, computer aided geometric design, and computational algebraic geometry.
Cite this article:

Xiaolong Yang,Xiaohong Jia. Simple primitive recognition via hierarchical face clustering. Computational Visual Media, 2020, 6(4): 431-443.

URL:

http://cvm.tsinghuajournals.com/10.1007/s41095-020-0192-6     OR     http://cvm.tsinghuajournals.com/Y2020/V6/I4/431

19], (b) Variational Mesh Segmentation (VMS) [11], (c) Feature-Aligned Segmentation (FAS) [20], and (d) our result. Colors are randomly assigned to segmented patches. (e) Error colormap. The color represents the distance from the point in the model to the fitted surface. Blue (value=0) indicates that the point is exactly located on the fitted surface, while red (value=1) indicates the largest distance between the fitted surface and the data point. Our result has better boundary smoothness and more meaningful extracted primitives, as highlighted.
">
Fig. 1 Comparisons with representative approaches: (a) Hierarchical Mesh Segmentation (HMS) [19], (b) Variational Mesh Segmentation (VMS) [11], (c) Feature-Aligned Segmentation (FAS) [20], and (d) our result. Colors are randomly assigned to segmented patches. (e) Error colormap. The color represents the distance from the point in the model to the fitted surface. Blue (value=0) indicates that the point is exactly located on the fitted surface, while red (value=1) indicates the largest distance between the fitted surface and the data point. Our result has better boundary smoothness and more meaningful extracted primitives, as highlighted.
Fig. 2 Clustering process for the Joint model with 445 faces. (a) Grey-green: input mesh. Orange: pair of faces with smallest clustering cost. (b) After reducing to 412 clusters. Planes are formed due to their higher priority. (c) At 166 clusters. All large planes have been extracted. (d) At 65 clusters. Cylinders are detected. (e) At 12 clusters; the final result corresponding to the ground truth. Clusters are randomly coloured.
Fig. 3 Fillet surfaces (red). (a) Approximate conical fillet surfaces between plane and cylinder clusters (white). The area of the planes and cylinders is much larger than that of the fillet part. (b) Approximate cylindrical fillet surfaces between plane clusters. The area of the planar part is much larger than that of the fillet part. We avoid merging such fillet surfaces clusters.
Fig. 4 (a) Two clusters (red and blue) to be merged; (b) the cylinder used as the final choice of primitive to approximate the merged area; (c)-(f) show the resulting primitive if instead the type is fixed as a plane, a cylinder, a sphere, and a cone.
i (red) and j (blue). (b) After merging, cluster (i,j) (green). Successive boundary edges make a turning angle, and a cluster with smooth boundaries has a smaller sum of edge turning angles.
">
Fig. 5 Sum of boundary turning angles. (a) Before merging, clusters i (red) and j (blue). (b) After merging, cluster (i,j) (green). Successive boundary edges make a turning angle, and a cluster with smooth boundaries has a smaller sum of edge turning angles.
19], VMS [11], FAS [20], ours, and a color map. Top to bottom: tessellated CAD models Chess and Sword, scanned mechanical model Cup, and organic shape Bone. Segmentation patches are randomly coloured.
">
Fig. 6 Comparisons, left to right, to HMS [19], VMS [11], FAS [20], ours, and a color map. Top to bottom: tessellated CAD models Chess and Sword, scanned mechanical model Cup, and organic shape Bone. Segmentation patches are randomly coloured.
Fig. 7 Further segmentation results produced by our algorithm. Segmentation patches are randomly coloured.
Fig. 8 Comparisons to HMS and VMS methods, for cone fitting. Left to right: input tessellated CAD model with sparse triangulation, results of HMS, VMS, our method, and colormap.
18] using the Venus_Body model with 5672 faces. Top: HFC results, bottom: our results, each method using its own boundary optimization. Left to right: with 18, 13, and 8 clusters.
">
Fig. 9 Boundary regularization comparison to the HFC method [18] using the Venus_Body model with 5672 faces. Top: HFC results, bottom: our results, each method using its own boundary optimization. Left to right: with 18, 13, and 8 clusters.
ModelMethodsB/D rate
Venus||18138
HFC7.4246.7965.316
Ours4.6303.1972.061
Sample||502817
HMS135.55095.67778.566
Ours115.24581.91172.652
Rockerarm||201610
HMS11.9739.3906.286
Ours7.4886.6665.473
Table 1 Boundary statistics. ||=number of clusters. B/D rate=(total boundary length)/(box diagonal length), which reflects complexity of clustering results relative to the input model
19]. Left: sample model with 50, 28, 17 clusters. Right: Rockerarm model with 20, 16, 10 clusters. Top: HMS results without boundary regularization. Bottom: our results.
">
Fig. 10 Comparison to the HMS method [19]. Left: sample model with 50, 28, 17 clusters. Right: Rockerarm model with 20, 16, 10 clusters. Top: HMS results without boundary regularization. Bottom: our results.
Fig. 11 Comparison to HMS in terms of priority, using the Joint model with 6060 faces. Left: Attene’s result without primitive priority. Right: ours with primitive priority.
Fig. 12 Comparison to HMS in terms of primitive priority using the Anchor (top) and the Fandisk (bottom) models. Left to right: ground truth, HMS result, and our result. The ground truth was provided by experts using manually segmentation.
Fig. 13 Comparison to deep learning approaches using the Ant model. Left to right: (a) STC, (b) LMVCNN, (c) our result, and (d) color map.
Fig. 14 Global optimization results for the Pinion model. Left to right: (a) input model, (b) initial result, and (c) result with global alignment.
Modelnf||HMSVMSFASOurs
Blade78k3571.35100.54122.1287.61
Chess24k814.8425.4527.4816.43
Cup5.7k52.515.826.643.46
Ant11.7k1212.2820.6222.4012.58
Dragknob0.3k6<12.632.96<1
Couplingdown3.7k367.7611.8113.558.98
Elk10k1315.7924.4528.1518.35
Bracket37k3822.1947.8145.7331.48
Dustpan4v701.579.149.822.75
Boat4k577.6615.3117.887.84
Screw0.3k9<14.624.68<1
Rockerarm7k209.2421.0429.875.92
Joint6k124.6214.8819.877.18
Fandisk13k2211.1921.8823.9516.99
Joint0.5k12<11.942.37<1
Sword80k8100.37190.17192.75132.47
Bone30k522.6334.1434.3425.47
Spool1.3k13<12.222.741.34
Rotor1.2k101.745.926.391.77
oblong0.8k24<11.561.47<1
Star10k2712.6326.9628.9315.58
Rollingstage100k3072.77124.82139.4790.76
M14527k6016.1228.8226.6616.55
Casting37k1618.5024.2324.4519.38
Sample26.7k1716.1224.9928.1522.04
Venus5.7k159.4114.5015.146.03
Anchor1k28<11.561.78<1
Moai20k2825.2237.634.0026.76
Table 2 Timings (s)
19], VMS [11], FAS [20], our method, and colormap, for 28 clusters.
">
Fig. 15 An unsatisfactory example. Left to right: results of HMS [19], VMS [11], FAS [20], our method, and colormap, for 28 clusters.
[1]   Várady, T.; Martin, R. R.; Cox, J. Reverse engineering of geometric models: An introduction. Computer-Aided Design Vol. 29, No. 4, 255-268, 1997.
[2]   Petitjean, S. A survey of methods for recovering quadrics in triangle meshes. ACM Computing Surveys Vol. 34, No. 2, 211-262, 2002.
[3]   Luo, L.; Baran, I.; Rusinkiewicz, S.; Matusik, W. Chopper: Partitioning models into 3D-printable parts. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 129, 2012.
[4]   Hu, R.; Li, H.; Zhang, H.; Cohen-Or, D. Approximate pyramidal shape decomposition. ACM Transactions on Graphics Vol. 33, No. 6, Article No. 213, 2014.
[5]   Lien, J. M.; Amato, N. M. Approximate convex decomposition of polyhedra and its applications. Computer Aided Geometric Design Vol. 25, No. 7, 503-522, 2008.
[6]   David, C.-S.; Pierre, A.; Mathieu, D. Variational shape approximation. ACM Transactions on Graphics Vol. 23, No. 3, , 2004.
doi: https://doi.org/10.1145/1015706.1015817
[7]   Wu, J.; Kobbelt, L. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum Vol. 24, No. 3, 277-284, 2005.
[8]   Julius, D.; Kraevoy, V.; Sheffer, A. D-charts: Quasi-developable mesh segmentation. Computer Graphics Forum Vol. 24, No. 3, 581-590, 2005.
[9]   Simari, P. D.; Singh, K. Extraction and remeshing of ellipsoidal representations from mesh data. In: Proceedings of Graphics Interface, 161-168, 2005.
[10]   Lu, L.; Choi, Y. K., Wang, W. P.; Kim, M. S. Variational 3D shape segmentation for bounding volume computation. Computer Graphics Forum Vol. 26, No. 3, 329-338, 2007.
[11]   Yan, D. M.; Wang, W. P.; Liu, Y.; Yang, Z. W. Variationalmesh segmentation via quadric surface fitting. Computer-Aided Design Vol. 44, No. 11, 1072-1082, 2012.
[12]   Kim, Y. M.; Mitra, N. J.; Yan, D. M.; Guibas, L. Acquiring 3D indoor environments with variability and repetition. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 138, 2012.
[13]   Katz, S.; Tal, A. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics Vol. 22, No. 3, 954-961, 2003.
[14]   Ji, Z.; Liu, L.; Chen, Z.; Wang, G. Easy mesh cutting.Computer Graphics Forum Vol. 25, No. 3, 283-291, 2006.
[15]   Lavoué, G.; Dupont, F.; Baskurt, A. A new CAD mesh segmentation method, based on curvature tensor analysis. Computer-Aided Design Vol. 37, No. 10, 975-987, 2005.
[16]   Yan, D. M.; Liu, Y.; Wang, W. P. Quadric surface extraction by variational shape approximation. In: Geometric Modeling and Processing - GMP 2006. Lecture Notes in Computer Science, Vol. 4077. Kim, M. S.; Shimada, K. Eds. Springer Berlin Heidelberg, 73-86, 2006.
[17]   Le, T.; Bui, G.; Duan, Y. A multi-view recurrent neural network for 3D mesh segmentation. Computers & Graphics Vol. 66, 103-112, 2017.
[18]   Garland, M.; Willmott, A.; Heckbert, P. S. Hierarchical face clustering on polygonal surfaces. In: Proceedings of the Symposium on Interactive 3D Graphics, 49-58, 2001.
[19]   Attene, M.; Falcidieno, B.; Spagnuolo, M. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer Vol. 22, No. 3, 181-193, 2006.
[20]   Zhuang, Y. X.; Dou, H.; Carr, N., Ju, T. Feature-aligned segmentation using correlation clustering. Computational Visual Media Vol. 3, No. 2, 147-160, 2017.
[21]   Shamir, A. A survey on mesh segmentation techniques. Computer Graphics Forum Vol. 27, No. 6, 1539-1556, 2008.
[22]   Kaiser, A.; Ybanez Zepeda, J. A.; Boubekeur, T. A survey of simple geometric primitives detection methods for captured 3D data. Computer Graphics Forum Vol. 38, No. 1, 167-196, 2019.
[23]   Fitzgibbon, A. W.; Eggert, D. W.; Fisher, R. B. High-level cad model acquisition from range images. Computer-Aided Design Vol. 29, No. 4, 321-330, 1997.
[24]   Vieira, M.; Shimada, K. Surface mesh segmentation and smooth surface extraction through region growing. Computer Aided Geometric Design Vol. 22, No. 8, 771-792, 2005.
[25]   Lloyd, S. Least squares quantization in PCM. IEEE Transactions on Information Theory Vol. 28, No. 2, 129-137, 1982.
[26]   Schnabel, R.; Wahl, R.; Klein, R. Efficient RANSAC for point-cloud shape detection. Computer Graphics Forum Vol. 26, No. 2, 214-226, 2007.
[27]   Li, H.; Wan, G. W.; Li, H. H.; Sharf, A.; Xu, K.; Chen, B. Q. Mobility fitting using 4D ransac. Computer Graphics Forum Vol. 35, No. 5, 79-88, 2016.
[28]   Lee, Y.; Lee, S.; Shamir, A.; Cohen-Or, D.; Seidel, H. P. Mesh scissoring with minima rule and part salience. Computer Aided Geometric Design Vol. 22, No. 5, 444-465, 2005.
[29]   Rodrigues, R. S. V.; Morgado, J. F. M.; Gomes, A. J. P. Part-based mesh segmentation: A survey. Computer Graphics Forum Vol. 37, No. 6, 235-274, 2018.
[30]   Lai, Y. K.; Hu, S. M.; Martin, R. R., Rosin, P. L. Rapid and effective segmentation of 3D models using random walks. Computer Aided Geometric Design Vol. 26, No. 6, 665-679, 2009.
[31]   Lafarge, F.; Keriven, R.; Brédif, M. Insertion of 3-D-primitives in mesh-based representations: Towards compact models preserving the details. IEEE Transactions on Image Processing Vol. 19, No. 7, 1683-1694, 2010.
[32]   Chen, X. B.; Golovinskiy, A., Funkhouser, T. A benchmark for 3D mesh segmentation. In: Proceedings of the ACM SIGGRAPH 2009 papers, Article No. 73, 2009.
[33]   Zheng, Y. Y.; Tai, C. L., Au, O. K. C. Dot scissor: A single-click interface for mesh segmentation. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 8, 1304-1312, 2012.
[34]   Au, O. K.-C.; Zheng, Y.; Chen, M.; Xu, P.; Tai, C.-L. Mesh segmentation with concavity-aware fields. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 7, 1125-1134, 2012.
[35]   Liu, R.; Zhang, H. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum Vol. 26, No. 3, 385-394, 2007.
[36]   Theologou, P.; Pratikakis, I.; Theoharis, T. Unsupervised spectral mesh segmentation driven by heterogeneous graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 39, No. 2, 397-410, 2017.
[37]   Ohtake, Y., Belyaev, A., Seidel, H. P. Ridge-valley lines on meshes via implicit surface fitting. ACM Transactions on Graphics Vol. 23, No. 3, 609-612, 2004.
[38]   Cao, Y. H.; Yan, D. M.; Wonka, P. Patch layout generation by detecting feature networks. Computers & Graphics Vol. 46, 275-282, 2015.
[39]   Dai, C.; Wang, C. C. L.; Wu, C.; Lefebvre, S.; Fang, G.; Liu, Y.-J. Support-free volume printing by multi-axis motion. ACM Transactions on Graphics Vol. 37, No. 4, Article No. 134, 2018.
[40]   Chen, X.; Li, H.; Fu, C.-W.; Zhang, H.; Daniel, C.-O.; Chen, B. 3D fabrication with universal building blocks and pyramidal shells. ACM Transactions on Graphics Vol. 37, No. 6, Article No. 189, 2018.
[41]   Kalogerakis, E.; Averkiou, M.; Maji, S.; Chaudhuri, S. 3D shape segmentation with projective convolutional networks. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 6630-6639, 2017.
[42]   Shu, Z. Y.; Qi, C. W.; Xin, S. Q.; Hu, C.; Wang, L.; Zhang, Y.; Liu, L. G. Unsupervised 3D shape segmentation and co-segmentation via deep learning. Computer Aided Geometric Design Vol. 43, 39-52, 2016.
[43]   Guo, K.; Zou, D. Q.; Chen, X. W. 3D mesh labeling via deep convolutional neural networks. ACM Transactions on Graphics Vol. 35, No. 1, Article No. 3, 2015.
[44]   Charles, R. Q.; Su, H.; Kaichun, M.; Guibas, L. J. Pointnet: Deep learning on point sets for 3D classification and segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 77-85, 2017.
[45]   Xu, H.; Dong, M.; Zhong, Z. Directionally convolutional networks for 3D shape segmentation. In: Proceedings of the IEEE International Conference on Computer Vision, 2698-2707, 2017.
[46]   Nan, L. L.; Xie, K.; Sharf, A. A search-classify approach for cluttered indoor scene understanding. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 137, 2012.
[47]   Dai, A.; Chang, A. X.; Savva, M.; Halber, M.; Funkhouser, T.; Niefiner, M. ScanNet: Richly-annotated 3D reconstructions of indoor scenes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2432-2443, 2017.
[48]   Nguyen, D. T.; Hua, B. S.; Yu, L. F.; Yeung, S. K. A robust 3D-2D interactive tool for scene segmentation and annotation. IEEE Transactions on Visualization and Computer Graphics Vol. 24, No. 12, 3005-3018, 2018.
[49]   Taubin, G. Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 13, No. 11, 1115-1138, 1991.
[50]   Huang, H. B.; Kalogerakis, E.; Chaudhuri, S.; Ceylan, D.; Kim, V. G.; Yumer, E. Learning local shape descriptors from part correspondences with multiview convolutional networks. ACM Transactions on Graphics Vol. 37, No. 1, Article No. 6, 2018.
[51]   Maron, H.; Galun, M.; Aigerman, N.; Trope, M.; Dym, N.; Yumer, E.; Kim, V.G.; Lipman. Convolutional neural networks on surfaces via seamless toric covers. ACM Transactions on Graphics Vol. 36, No. 4, Article No. 71, 2017.
[52]   Mitra, N. J.; Guibas, L. J.; Pauly, M. Partial and approximate symmetry detection for 3D geometry. ACM Transactions on Graphics Vol. 25, No. 3, 560-568, 2006.
[1] Dawar Khan, Dong-Ming Yan, Fan Ding, Yixin Zhuang, Xiaopeng Zhang. Surface remeshing with robust user-guided segmentation[J]. Computational Visual Media, 2018, 4(2): 113-122.
[2] Johannes Furch, Anna Hilsmann, Peter Eisert. Surface tracking assessment and interaction in texture space[J]. Computational Visual Media, 2018, 4(1): 3-15.
[3] Zherong Pan, Dinesh Manocha. Editing smoke animation using a deforming grid[J]. Computational Visual Media, 2017, 3(4): 369-378.
[4] Yixin Zhuang,Hang Dou,Nathan Carr,Tao Ju. Feature-aligned segmentation using correlation clustering[J]. Computational Visual Media, 2017, 3(2): 147-160.
[5] Weize Quan,Jianwei Guo,Dong-Ming Yan,Weiliang Meng,Xiaopeng Zhang. Analyzing surface sampling patterns using the localized pair correlation function[J]. Computational Visual Media, 2016, 2(3): 219-230.
[6] Yuen-Shan Leung,Xiaoning Wang,Ying He,Yong-Jin Liu,Charlie C. L. Wang. A unified framework for isotropic meshing based on narrow-band Euclidean distance transformation[J]. Computational Visual Media, 2015, 1(3): 239-251.