Fast topological reconstruction algorithm for a STL file

doi:10.11772/j.issn.1001-9081.2014.09.2716

Abstract

Abstract:

Because the lack of the necessary topological relation between graphic factors, through analyzing the STL (Stereolithographic) format file and reading it, and using the hash table as a lookup table, the topological relation among various elements of three-dimensional model is quickly created. Using the Hash table, this algorithm created the point table and the surface table for the elements, and realized the topological reconstruction. The time complexity of this algorithm is O(n), while the space complexity of this algorithm is O(3n+(4+m)f+m). Finally, the algorithm was compared with the direct algorithm and red-black tree algorithm through five examples, and the results show that the proposed algorithm costs less time and the model with 650 thousand triangular facets can be reconstructed within 2.3 seconds on PC.

摘要：

针对立体光刻(STL)文件所表示的图形要素之间缺乏必要的拓扑关系，对STL格式文件进行分析和读取，以哈希表作为查找表快速建立三维模型各要素间的拓扑关系，建立能表示要素关系的点表和面表，利用基于哈希表的拓扑重建算法实现了拓扑结构的快速建立, 算法时间复杂度仅为O(n), 空间复杂度为O(3n+(4+m)f+m)。最后，列举5个实例进行验证测试，实验结果显示，与直接算法和红黑树法相比，所提出的算法用时更少，在普通计算机上重建含有65万个三角面片模型的拓扑结构只需2.3s。

CLC Number:

TP391

WANG Zengbo. Fast topological reconstruction algorithm for a STL file[J]. Journal of Computer Applications, 2014, 34(9): 2720-2724.

王增波. STL格式文件的快速拓扑重建算法[J]. 计算机应用, 2014, 34(9): 2720-2724.

References

［1］CHEN Y, GAO D Z, NIE C, et al.Bayesian statistical reconstruction for low-dose X-ray computed tomography using an adaptive-weighting nonlocal prior ［J］. Computerized Medical Imaging and Graphics, 2009, 33(7): 495-500.

［2］RUST G F, AURICH V, REISER M. Noise dose reduction and image improvements in screening virtual colonoscopy with tube currents of 20 mAs with nonlinear Gaussian filter chains ［C］// Proceedings of Medical Imaging 2002: Physiology and Function from Multidimensional Images. Bellingham: SPIE, 2002: 186-197.

［3］〖CM(27〗GUI Z G, LIU Y. Noise reduction for low-dose X-ray computed tomography with fuzzy filter ［J］. Optik — International Journal for Light and Electron Optics, 2012, 123(13): 1207-1211.

［4］MA J, HUANG J, CHEN Y, et al.Generalized Gibbs prior based high quality low-dose X-CT reconstruction ［J］. Computer Engineering and Applications, 2008, 44(16): 4-7. (马建华，黄静，陈阳，等.基于广义Gibbs先验的低剂量X-CT优质重建研究［J］.计算机工程与应用,2008,44(16):4-7.)

［5］ZHANG Q, GUI Z G, CHEN Y, et al.Bayesian sinogram smoothing with an anisotropic diffusion weighted prior for low-dose X-ray computed tomography ［J］. Optik — International Journal for Light and Electron Optics, 2013, 124(17): 2811-2816.

［6］LIU Y, ZHANG Q, GUI Z. Noise reduction for low-dose CT sinogram based on fuzzy entropy ［J］. Journal of Electronics and Information, 2013, 35(6): 1421-1427. (刘祎，张权，桂志国.基于模糊熵的低剂量CT投影降噪算法研究［J］.电子与信息学报,2013,35(6):1421-1427.)

［7］WANG J, LI T F, LU H B, et al.Penalized weighted least-squares approach to sinogram noise reduction and image reconstruction for low-dose X-Ray computed tomography ［J］. IEEE Transactions on Medical Imaging, 2006, 25(10): 1272-1283.

［8］La RIVIERE P J. Penalized-likelihood sinogram smoothing for low dose CT ［J］. Medica Physics, 2005, 32(6): 1676-1683.

［9］LI T, LI X, WANG J, et al.Nonlinear sinogram smoothing for low-dose X-ray CT ［J］. IEEE Transactions on Nuclear Science, 2004, 51(5): 2505-2513.

［10］PERONA P, MALIK J. Scale space and edge detection using anisotropic diffusion ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1990, 12(7): 629-639.

［11］CHEN Q, ZHENG Y, SUN Q, et al.Patch similarity based anisotropic diffusion for image denoising ［J］. Journal of Computer Research and Development, 2010, 47(1): 33-42. (陈强，郑钰辉，孙权森，等.片相似性各向异性扩散图像去噪［J］.计算机研究与发展，2010，47(1)：33-42.)

［12］〖CM(26*2〗LING J, BOVIK A C. Smoothing low-SNR molecular images via anisotropic median-diffusion ［J］. IEEE Transactions on Medical Imaging, 2002, 21(4): 377-384.

［13］BYRNE C L. Block-iterative methods for image reconstruction from projections ［J］. IEEE Transactions on Image Processing, 1996, 5(5): 792-794.

［14］CHAO S M, TSAI D M. An improved anisotropic diffusion model for detail and edge preserving smoothing ［J］. Pattern Recognition Letters, 2010, 31(13): 2012-2023.

［15］BUADES A, MOREL J M. A review of image denoising algorithms with a new one ［J］. Multiscale Model and Simulation, 2005, 4(2):490-530.

[1]	. Pavement defect detection algorithm with enhanced morphological perception [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	YANG Jianfeng, CHEN Bin, LI Yuxuan. Self-supervised point cloud anomaly detection method based on point cloud reconstruction [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	XUE Zhenhua, LI Qiang, HUANG Chao. Vision foundation model-driven pixel-level image anomaly detection model [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Binocular vision object location algorithm for robot arm grasping [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	. Multi-attention contrastive learning for infrared small target detection [J]. Journal of Computer Applications, 0, (): 0-0.
[6]	LI Zhonghua, ZHONG Gengxin, FAN Ping, ZHU Hengliang. Camouflaged object detection by boundary mining and background guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[7]	. Multi-view difficult airway recognition based on discriminant region guidance [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	. Privacy preserving localization of surveillance images based on large vision models [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	. Gravity data denoising method based on multilevel wavelet residual network#br# #br# [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Data augmentation method for abnormal passenger behavior in elevators based on dynamic graph convolutional network [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Text-based person retrieval method based on multi-granularity shared semantic center association [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	ZHANG Qing, YANG Fan, FANG Yuhan. Chinese Spelling Correction Algorithm Based on Multi-Modal Information Fusion [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	WANG Hao, WANG Jinwei, CHENG Xin, ZHANG Jiawei, WU Hao, LUO Xiangyang, MA Bin. A Review of JPEG Recompression Forensics for Color Images [J]. Journal of Computer Applications, 0, (): 0-0.
[14]	. Distribution adaptation and dynamic curriculum pseudo-labeling framework for semi-supervised fire detection [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	. Multimodal harmful content detection method based on weakly supervised modality semantic enhancement [J]. Journal of Computer Applications, 0, (): 0-0.