Please wait a minute...
浙江大学学报(工学版)
JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE)  2018, Vol. 52 Issue (3): 605-612    DOI: 10.3785/j.issn.1008-973X.2018.03.025
Artificial Intelligence and Graphics     
Intersection algorithm of point cloud surface by spatial mesh and refinement
ZHENG Peng-fei1,2, ZOU Pei-ling1, ZHAO Ju-di1, LIN Da-jun1, AN Qi1
1. School of Mechanical and Power Engineering, East China University of Science and Technology, Shanghai 200237, China;
2. School of Mechanical Information, Yiwu Industrial & Commercial College, Yiwu 322000, China
Download:   PDF(9153KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

An intersection algorithm of point cloud surface by spatial mesh and refinement was proposed according to the analysis of the advantages and disadvantages of the existing methods of computing line of intersection. The discrete method was used to express the geometric graphic; intersection lines between the graphics were computed by intersection or coincidence degree of discrete points. The intersection region of the point cloud surface was quickly located by the space meshing envelope boxes. The point clouds in the intersection were refined by calculating the triangles' centre-of-gravity position. The validity of the proposed algorithm was verified by computing the intersection line in practical point cloud models. Results show that the proposed algorithm is simple, accurate, stable and reliable, with wide adaptability.

Received: 24 June 2017      Published: 11 September 2018
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

ZHENG Peng-fei, ZOU Pei-ling, ZHAO Ju-di, LIN Da-jun, AN Qi. Intersection algorithm of point cloud surface by spatial mesh and refinement. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(3): 605-612.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2018.03.025     OR     http://www.zjujournals.com/eng/Y2018/V52/I3/605


点云曲面空间网格化加密求交算法

通过分析现有图形截交线、相贯线求解方法的优缺点，提出一种点云曲面空间网格化加密求交算法.采用几何图形离散化表达，并采用离散点求交集或重合度的方式计算图形间的公共部分.用空间网格包络盒快速定位点云曲面的相交区域，并采用计算三角面的重心位置，对相交区域进行点云加密.通过实际点云模型算例，验证该算法的有效性.经试验证明，所设计的算法操作简单、计算精度高、稳定可靠、适应性广.

[1] 张晓东,王园宇,郝鹏飞,等.相贯线及其展开曲线的方程构建方法的研究[J].机械设计与研究,2008,4(2):21-24. ZHANG Xiao-dong, WANG Yuan-yu, HAO Peng-fei, et al. Study of establishing the equations of intersecting line and its developmental figure[J]. Machine Design and Research,2008,4(2):21-24.
[2] 刘德刚,吴兴群,李佳星.基于VTK的相贯线坐标计算方法研究[J].现代制造工程,2016(3):59-63. LIU De-gang,WU Xing-qun,LI Jia-xing. Intersection calculation method research based on VTK[J]. Modern Manufacturing Engineering,2016(3):59-63.
[3] 韩淑洁.快速准确作截交线的通用方法研究[J].机械工程与自动化,2012,10(5):201-204. HAN Shu-jie. A general method of drawing intersection line rapidly and accurately[J]. Mechanical Engineering & Automation, 2012,10(5):201-204.
[4] 杨绪利.圆锥截交线的形状及投影分析[J].东华大学学报:自然科学版,2005,8(4):76-78. YANG Xu-li. On the form and projection analysis of conic cut and hand in line[J]. Journal of Dong-hua University, 2005,8(4):76-78.
[5] 朱建宁,王敏杰,魏兆成,等.快速计算平面与高精度细分曲面交线的方法[J].计算机集成制造系统,2014,6(20):1322-1329. ZHU Jian-ning, WANG Min-jie, WEI Zhao-cheng et al. Efficient algorithm for computing intersection curve between plane and subdivision surface[J]. Computer Integrated Manufacturing Systems, 2014,6(20):1322-1329.
[6] 李慧莹,陈良骥.基于四边形网格参数细分的平面与自由曲面求交算法[J].机电工程,2013,8(30):956-970. LI Hui-ying, CHEN Liang-ji. Algorithm for finding plane & free-form surface intersection curve based on subdivision of quadrilateral mesh parameters[J]. Journal of Mechanical & Electrical Engineering, 2013,8(30):956-970.
[7] 曹斌,王敏杰,朱建宁.快速计算高精度细分曲面之间交线的方法[J].计算机集成制造系统,2014,9(20):2079-2085. CAO Bin, WANG Min-jie, ZHU Jian-ning. Efficient algorithm for computing intersection curve between subdivision surfaces[J]. Computer Integrated Manufacturing Systems, 2014,9(20):2079-2085.
[8] 孙殿柱,孙永伟,田中朝,等.三角网格曲面模型快速求交算法[J].北京工业大学学报,2012,8(38):1121-1135. SUN Dian-zhu,SUN Yong-wei,TIAN Zhong-chao, et al. Rapidly getting intersection algorithm for triangular mesh surface models[J]. Journal of Bei-jing University of Technology, 2012,8(38):1121-1135.
[9] 李宁,田震,张立华,等. 优化的三角网格曲面求交算法[J].辽宁工程技术大学学报:自然科学版,2013,9(32):1269-1273. LI Ning, TIAN Zhen, ZHANG Li-hua et al. Optimization algorithm for triangular mesh surface intersection[J]. Journal of Liao-ning Technical University:Natural Science, 2013,9(32):1269-1273.
[10] 付明珠,罗钟铉,冯二宝.基于微分几何的隐式曲面交线跟踪方法[J].计算机辅助设计与图形学学报,2016,4(28):556-564. FU Ming-zhu, LUO Zhong-xuan, FENG Er-bao. Tracing implicit surface intersection based on differential geometry[J]. Journal of Computer-Aided Design & Computer Graphics, 2016,4(28):556-564.
[11] SKODA A. A new algorithm for the intersection of a line with the independent set polytope of a matroid[J]. Bulletin Des Sciences Mathematiques, 2009, 133(2):169-185.
[12] MARIN G, JON R. Computing line intersections[J]. International Journal of Image and Graphics, 2001, 1(2):217-230.
[13] 段明德,郑立霞,李明利,等.基于逆向几何求交算法的STL模型多孔结构体素化[J].河南理工大学学报:自然科学版,2017,1(36):86-90. DUAN Ming-de,ZHENG Li-xia,LI Ming-li et al. Porous structure voxelization for STL model based on reverse geometrical intersection[J]. Journal of He-nan Polytechnic University:Nature Science, 2017,1(36):86-90.
[14] SABHARWAL C L, LEOPOLD J L. A triangle-triangle intersection algorithm[J]. Computer Science & Information Technology, 2015, 5(11):27-35.
[15] WANG W, GOLDMAN R, TU C. Enhancing Levin's method for computing quadric-surface intersections[J]. Computer Aided Geometric Design, 2003, 20(7):401-422.
[16] TEIXEIRA F G, CREUS G J. A robust algorithm to determine surface/surface intersection in both parametric spaces[J]. Mecnica Computacional, 2008(41):3093-3115.
[17] CHRISMIANTO D, KIM D J. Parametric bulbous bow design using the cubic Bezier curve and curve-plane intersection method for the minimization of ship resistance in CFD[J]. Journal of Marine Science & Technology, 2014, 19(4):479-492.
[18] JIA X, WANG W, CHOI Y K, et al. Continuous detection of the variations of the intersection curve of two moving quadrics in 3-Dimensional projective space[J]. Journal of Symbolic Computation, 2016, 73(C):221-243.
[19] FU Q, WU Z, WANG X, et al. An algorithm for finding intersection between ball B-spline curves[J]. Journal of Computational & Applied Mathematics, 2017,327:260-273.
[20] SHEN J, ALLIEZ P, DODGSON N. A line/trimmed NURBS surface intersection algorithm using matrix representations[J]. Computer Aided Geometric Design, 2016, 48(C):1-16.
[21] ALÉSSIO O, DVLDVL M, DVLDVL B U, et al. Differential geometry of non-transversal intersection curves of three parametric hypersurfaces in Euclidean 4-space[J]. Computer Aided Geometric Design, 2014, 31(9):712-727.
[22] SEO D, JUNG H, SUNG W K, et al. Development of the Korean spine database and automatic surface mesh intersection algorithm for constructing e-Spine simulator[J]. Journal of Applied Mathematics, 2014, 2014(9):1-11.
[1] HAN Yong, NING Lian-ju, ZHENG Xiao-lin, LIN Wei-hua, SUN Zhong-yuan. Matrix factorization recommendation based on social information and item exposure[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2019, 53(1): 89-98.
[2] ZHENG Zhou, ZHANG Xue-chang, ZHENG Si-ming, SHI Yue-ding. Liver segmentation in CT images based on region-growing and unified level set method[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2382-2396.
[3] ZHAO Li-ke, ZHENG Shun-yi, WANG Xiao-nan, HUANG Xia. Rigid object position and orientation measurement based on monocular sequence[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(12): 2372-2381.
[4] HE Jie-guang, PENG Zhi-ping, CUI De-long, LI Qi-rui. Teaching-learning-based optimization algorithm with local dimension improvement[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2159-2170.
[5] LI Zhi, SHAN Hong, MA Tao, HUANG Jun. Group discovery of mobile terminal users based on reverse-label propagation algorithm[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(11): 2171-2179.
[6] WANG Shuo-peng, YANG Peng, SUN Hao. Construction process optimization of fingerprint database for auditory localization[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(10): 1973-1979.
[7] WEI Xiao-feng, CHENG Cheng-qi, CHEN Bo, WANG Hai-yan. Chain code based on independent edge number[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1686-1693.
[8] CHEN Rong-hua, WANG Ying-han, BU Jia-jun, YU Zhi, GAO Fei. Website accessibility sampling evaluation based on KNN and local regression[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1702-1708.
[9] ZHANG Cheng-zhi, FENG Hua-jun, XU Zhi-hai, LI Qi, CHEN Yue-ting. Piecewise noise variance estimation of images based on wavelet transform[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(9): 1804-1810.
[10] LIU Zhou-zhou, LI Shi-ning, LI Bin, WANG Hao, ZHANG Qian-yun, ZHENG Ran. New elastic collision optimization algorithm and its application in sensor cloud resource scheduling[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1431-1443.
[11] WANG Yong-chao, ZHU Kai-lin, WU Qi-xuan, LU Dong-ming. Adaptive display technology of high precision model based on local rendering[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1461-1466.
[12] SUN Nian, LI Yu-qiang, LIU Ai-hua, LIU Chun, LI Wei-wei. Microblog sentiment analysis based on collaborative learning under loose conditions[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1452-1460.
[13] ZHENG Shou-guo, CUI Yan-min, WANG Qing, YANG Fei, CHENG Liang. Design of field data acquisition platform for aircraft assembly[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(8): 1526-1534.
[14] BI Xiao-jun, WANG Chao. Many-objective evolutionary algorithm based on hyperplane projection[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1284-1293.
[15] ZHANG Ting-rong, TENG Qi-zhi, LI Zheng-ji, QING Lin-bo, HE Xiao-hai. Super-resolution reconstruction for three-dimensional core CT image[J]. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 2018, 52(7): 1294-1301.