Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds

LI Guojun; LI Zongchun; SUN Yuanchao; LI Wei; HUANG Zhiyong

doi:10.13203/j.whugis20140513

Volume 42 Issue 1

Jan. 2017

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2017 > 42(1): 123-129. > DOI: 10.13203/j.whugis20140513

LI Guojun, LI Zongchun, SUN Yuanchao, LI Wei, HUANG Zhiyong. Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1): 123-129. DOI: 10.13203/j.whugis20140513

Citation:

PDF (984 KB)

Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds

1.
School of Mapping and Surveying, Information Engineering University, Zhengzhou 450052, China
2.
Beijing Satellite Navigation Center, Beijing 100094, China
3.
China Aerospace Surveying & Mapping Center, Beijing 102102, China

More Information

Author Bio:
LI Guojun, master, specializes in surface reconstruction and time-frequency measurement. E-mail:1010551750@qq.com
Received Date: August 03, 2015
Published Date: January 04, 2017

Graphical Abstract

Abstract

Abstract

To reconstruct surface from noisy point clouds, a surface reconstruction algorithm based on Delaunay refinement was proposed. Firstly, the local surface was approximated by algebraic sphere, which was fitted through neighbor point coordinates and normals by robust least square algorithm. Compared with traditional sphere fitting methods, the new method is more robust to noises and outliers. Secondly, to find any segment intersect with surface for Delaunay refinement procedure, the surface bounding spheres intersected with segment were efficiently founded with AABB-tree. Then, initialized with sphere center, the first approximated segment-surface intersections within bounding spheres were parallel-computed by iterative segment-sphere intersection. Finally, the surface was meshed by Delaunay refinement, which is not ambiguous and can reconstruct surface with good aspect ratio comparing with Marching-cube algorithm. Experiments show that the new algorithm can efficiently, robustly and accurately reconstruct surface from point clouds with high noises. But its time and memory consuming will rapidly increase for precise models.
- Delaunay refinement,
- sphere fitting,
- noisy point clouds,
- surface reconstruction

FullText(HTML)

References (21)

References

[1]	朱德海.点云库PCL学习教程[M].北京:北京航空航天大学出版社, 2012, 359-360 Zhu Dehai. Point Cloud Library PCL Learning Tutorial[M]. Beijing:Beihang University Press, 2012, 359-360
[2]	Amenta N, Choi S, Kolluri R K. The Power Crust, Unions of Balls, and the Medial Axis Transform[J]. Computational Geometry, 2001, 19(2):127-153
[3]	Dey T K, Goswami S. Provable Surface Reconstruction from Noisy Samples[C]. The Twentieth Annual Symposium on Computational Geometry, Brooklyn, NY, 2004
[4]	Kuo C, Yau H. A Delaunay-Based Region-Growing Approach to Surface Reconstruction from Unorganized Points[J]. Computer-Aided Design, 2005, 37(8):825-835 doi: 10.1016/j.cad.2004.09.011
[5]	张剑清, 李彩林, 郭宝云.基于切平面投影的散乱数据点快速曲面重建算法[J].武汉大学学报·信息科学版, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml Zhang Jianqing, Li Cailin, Guo Baoyun. A Fast Surface Reconstruction Algorithm for Unorganized Points Based on Tangent Plane Projection[J]. Geomatics and Information Science of Wuhan University, 2011, 36(7):757-762 http://ch.whu.edu.cn/CN/abstract/abstract595.shtml
[6]	Yau H, Yang T, Jian H. A Region-Growing Algorithm Using Parallel Computing for Surface Reconstruction from Unorganized Points[J]. Advances in Engineering Software, 2013, 59:29-37 doi: 10.1016/j.advengsoft.2013.03.002
[7]	Alexa M, Behr J, Cohen-Or D, et al. Point Set Surfaces[C]. The Conference on Visualization, San Diego, California, USA, 2001
[8]	Guennebaud G, Gross M. Algebraic Point Set Surfaces[C]. ACM Transactions on Graphics, San Diego, 2007
[9]	Campos R, Garcia R, Alliez P, et al. Splat-Based Surface Reconstruction from Defect-Laden Point Sets[J]. Graphical Models, 2013, 75(6):346-361 doi: 10.1016/j.gmod.2013.08.001
[10]	Kazhdan M, Bolitho M, Hoppe H. Poisson Surface Reconstruction[C]. The Fourth Eurographics Symposium on Geometry Processing, Cagliari, 2006
[11]	Alliez P, Cohen-Steiner D, Tong Y, et al. Voronoi-Based Variational Reconstruction of Unoriented Point Sets[C]. Symposium on Geometry Processing, Barcelona, Spain, 2007
[12]	Mullen P, de Goes F, Desbrun M, et al. Signing the Unsigned:Robust Surface Reconstruction from Raw Pointsets[C]. Computer Graphics Forum, Lyon, France, 2010
[13]	Giraudot S, Cohen-Steiner D, Alliez P. Noise-Adaptive Shape Reconstruction from Raw Point Sets[C]. Computer Graphics Forum, Genova, Italy, 2013
[14]	Gander W, Golub G H, Strebel R. Least-Squares Fitting of Circles and Ellipses[J]. BIT Numerical Mathematics, 1994, 34(4):558-578 doi: 10.1007/BF01934268
[15]	Pratt V. Direct Least-Squares Fitting of Algebraic Surfaces[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4):145-152 doi: 10.1145/37402
[16]	Yuanxi Y. Robust Estimation for Dependent Observations[J]. Manuscripta Geodaetica, 1994, 19(1):10-17
[17]	Adamson A, Alexa M. Approximating and Intersecting Surfaces from Points[C]. The 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Aachen, 2003
[18]	Boissonnat J, Oudot S. Provably Good Sampling And Meshing of Surfaces[J]. Graphical Models, 2005, 67(5):405-451 doi: 10.1016/j.gmod.2005.01.004
[19]	Lorensen W E, Cline H E. Marching Cubes:A High Resolution 3D Surface Construction Algorithm[C]. The 14th Annual Conference on Computer Graphics and Interactive Techniques, Anaheim, 1987
[20]	CGAL. Computational Geometry Algorithm Library[EB/OL]. http://www.cgal.org, 2015
[21]	Béchet E, Cuilliere J, Trochu F. Generation of a Finite Element MESH from Stereolithography (STL) Files[J]. Computer-Aided Design, 2002, 34(1):1-17 doi: 10.1016/S0010-4485(00)00146-9

[1]	ZHANG Kaishi, JIAO Wenhai, LI Jianwen. Analysis of GNSS Positioning Precision on Android Smart Devices[J]. Geomatics and Information Science of Wuhan University, 2019, 44(10): 1472-1477. DOI: 10.13203/j.whugis20180085
[2]	ZHANG Xiaohong, LIU Gen, GUO Fei, LI Xin. Model Comparison and Performance Analysis of Triple-frequency BDS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2018, 43(12): 2124-2130. DOI: 10.13203/j.whugis20180078
[3]	KONG Yao, SUN Baoqi, YANG Xuhai, CAO Fen, HE Zhanke, YANG Haiyan. Precision Analysis of BeiDou Broadcast Ephemeris by Using SLR Data[J]. Geomatics and Information Science of Wuhan University, 2017, 42(6): 831-837. DOI: 10.13203/j.whugis20140856
[4]	ZHANG Xiaohong, DING Lele. Quality Analysis of the Second Generation Compass Observables and Stochastic Model Refining[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 832-836.
[5]	ZHANG Xiaohong, GUO Fei, LI Pan, ZUO Xiang. Real-time Quality Control Procedure for GNSS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2012, 37(8): 940-944.
[6]	CAI Changsheng, ZHU Jianjun, DAI Wujiao, KUANG Cuilin. Modeling and Result Analysis of Combined GPS/GLONASS Precise Point Positioning[J]. Geomatics and Information Science of Wuhan University, 2011, 36(12): 1474-1477.
[7]	HE Ning, WANG Lei. Recursion Multi-service Cross-layer Flow Control Algorithm of Broadband GEO Satellite Networks[J]. Geomatics and Information Science of Wuhan University, 2010, 35(5): 532-536.
[8]	CAI Hua, ZHAO Qile, LOU Yidong. Implementation and Precision Analysis of GPS Precise Clock Estimation System[J]. Geomatics and Information Science of Wuhan University, 2009, 34(11): 1293-1296.
[9]	DAI Wujiao, DING Xiaoli, ZHU Jianjun. Comparing GPS Stochastic Models Based on Observation Quality Indices[J]. Geomatics and Information Science of Wuhan University, 2008, 33(7): 718-722.
[10]	ZHANG Yongjun, ZHANG Yong. Analysis of Precision of Relative Orientation and Forward Intersection with High-overlap Images[J]. Geomatics and Information Science of Wuhan University, 2005, 30(2): 126-130.

Cited By

Cited by

Periodical cited type(28)

1.	李岚，朱锋，刘万科，张小红. 城市分类场景的GNSS伪距随机模型构建及其定位性能分析. 武汉大学学报(信息科学版). 2025(03): 545-553 .
2.	苑晓峥，徐爱功，高猛，祝会忠. 基于低成本终端抗差速度约束差分定位算法. 大地测量与地球动力学. 2024(01): 27-34 .
3.	曲利红，李俊芹. 通用智能技术路线下的人机传播应用. 电视技术. 2024(03): 176-179 .
4.	刘一，刘敏，边少锋，翟国君，周威. 北斗低成本接收机单频PPP海上定位性能分析. 海洋测绘. 2024(03): 68-72+82 .
5.	张宝，吴泓正，邸越超，张传定. Android智能手机GNSS定位研究进展. 测绘科学. 2024(05): 1-14 .
6.	侯雪，张献志，叶远斌. 基于GDCORS的北斗终端高精度定位算法实现及性能分析. 地理空间信息. 2024(08): 72-75 .
7.	孙俊锋，穆宏波，于先文，廖鹏，吴焱泽. 顾及系统误差影响的智能手机GNSS观测值质量分析. 测绘工程. 2024(05): 43-49 .
8.	孙俊锋，吴焱泽，于先文，廖鹏，叶嘉宁，曹嘉瑞. 基于北斗的智能手机内河航道高精度定位软件研发. 现代测绘. 2024(03): 13-17 .
9.	尹昊华，雷博，连宏亮，徐邦岁，曾翔强. 基于安卓智能手机的高精度定位系统研发及测试. 国土资源导刊. 2024(03): 9-17 .
10.	祝会忠，孙沐凡，李军. GNSS低成本智能终端抗差自适应差分定位算法. 导航定位学报. 2024(06): 10-19 .
11.	王瑞光，王中元，胡超，王阳阳，刘冰雨. 智能手机BDS-3/GPS数据质量及SPP性能分析. 大地测量与地球动力学. 2023(02): 168-172 .
12.	孟庆庆，郭德普，胡洁，薄伟伟. 移动GIS在黄委直管河道确权划界中的应用. 水利信息化. 2023(02): 44-49 .
13.	徐彦田，刘巍峰，李玉星，姜鼎璇. BDS/GPS/GAL智能手机RTK动态定位算法. 无线电工程. 2023(05): 1061-1067 .
14.	王甫红，栾梦杰，程雨欣，祝浩祈，赵广越，张万威. 城市环境下智能手机车载GNSS/MEMS IMU紧组合定位算法. 武汉大学学报(信息科学版). 2023(07): 1106-1116 .
15.	郑东，汪梦月，杨中皇. SM3国密算法在Android内核的汇编语言快速实现. 西安邮电大学学报. 2023(03): 57-62 .
16.	逯遥，聂志喜，王振杰，徐晓飞，张远帆，王翔. 单/双频混合数据的Android手机精密单点定位方法. 测绘科学. 2023(08): 64-71+129 .
17.	傅鑫榕，王甫红，郭磊，栾梦杰，祝浩祈. 不同电离层模型对智能手机实时PPP精度的影响分析. 测绘地理信息. 2023(06): 26-31 .
18.	葛在宸，王明华. 基于智能手机GNSS伪距定位的运动距离和速度确定. 江西科学. 2023(06): 1124-1130 .
19.	邱树素，顾桢，章怿钦，叶俊华. 基于手机内置传感器的相对高程模型. 北京测绘. 2023(12): 1676-1682 .
20.	董少敏，辛宪会，刘杰，陈文哲，卢为选. 便携式GNSS接收机集成方案及其定位精度分析. 海洋测绘. 2022(03): 56-60 .
21.	甘露，王志斌，张少波，韩明敏，陈攀，黄威翰. Android智能手机间相对定位性能分析. 测绘工程. 2022(05): 54-60 .
22.	李阿红. 基于混合神经网络的Android软件缺陷精准预测研究. 自动化与仪器仪表. 2022(08): 33-36+41 .
23.	张小红，陶贤露，王颖喆，刘万科，朱锋. 城市场景智能手机GNSS/MEMS融合车载高精度定位. 武汉大学学报(信息科学版). 2022(10): 1740-1749 .
24.	王怡欣，刘晖，钱闯，范潇云. 一种基于智能手机的实时高精度定位系统开发与车载应用测试. 测绘通报. 2022(10): 56-61 .
25.	曾树林，匡翠林. 智能手机RTK定位软件实现及应用试验. 全球定位系统. 2022(05): 72-80 .
26.	祝会忠，李骏鹏，李军. 智能手机GNSS多系统多频实时动态定位方法. 测绘科学. 2022(09): 8-19 .
27.	舒宝，义琛，王利，许豪，田云青. 华为P30手机GPS/BDS/GLONASS/Galileo观测值随机模型优化及定位性能分析. 大地测量与地球动力学. 2022(12): 1222-1226 .
28.	吴文坛，秘金钟，谷守周. 智能手机广域差分实时定位分析. 测绘科学. 2022(10): 39-44 .

Other cited types(27)

Get Citation

PDF

XML

Article views (2531) PDF downloads (338) Cited by(55)

Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds

Abstract

References

Related Articles

Cited by

Periodical cited type(28)

Other cited types(27)

Catalog

Related

Using Delaunay Refinement to Reconstruct Surface from Noisy Point Clouds

Abstract

References

Related Articles

Cited by

Periodical cited type(28)

Other cited types(27)

Catalog

Related

Export File

Citation

Format

Content