海量数据点三维重构关键技术研究与应用
|
摘要
逆向工程中基于点云的三维模型重建，在许多应用中具有重要意义。然而测量系统和三维CAD系统之间无法直接结合，因为测量得到的数据是海量散乱点，三维CAD无法对之进行高效处理。这成为逆向工程的一个瓶颈。本论文研究设计一个Test3D软件，其设计思想是：第一步作为三维扫描仪器和三维CAD软件的接口模块，搭起二者之间的桥梁，然后在此基础上研究直接由点云做面的处理方法，目的是通过对点云处理后能直接输出可供CAM软件使用的曲面模型。
本论文的第一章对逆向工程进行了简单介绍，说明了本论文研究内容在逆向工程中所处的位置，并简单介绍要重点研究的内容。第二章先简单描述了Test3D软件的基本功能，然后介绍了三维图形编程所需要的一些基本理论。第三章介绍了软件中用到的三项关键技术：面向对象技术、OpenGL以及多线程编程技术。第四章对由离散点构建曲线进行了研究，绕过高阶矩阵求逆，把由k个低阶的Bezier曲线拼合产生的复合曲线来代替单一的高阶Bezier曲线，并保证曲线之间的光滑过渡。第五章研究了如何自动由点云寻找特征点云带。通过寻找邻近点计算曲率，并通过曲率大小得到特征点云带。第六章探讨了由海量散乱点重构曲面的技术，并提出了一种简单高效的曲面重构方法。第七章介绍了IGES接口，并说明如何实现这种接口。第八章对全文进行了总结
3D model reconstruction based on point-clouds in reverse engineering has significant application in many areas. However, measurement system can not link with 3D CAD system directly because the measured dense scattered data can not be processed effectively by 3D CAD software. This is a choke point in reverse engineering. This paper researches and designs a software named Test3D. The following is the main ideas: firstly, it should become the linked part between measurement system and 3D CAD system. Then, it should can reconstruct surface from point-clouds directly in order to output surface model that can be used by CAM software directly.
In this paper, the chapter 1 introduces the concept of reverse engineering, shows the position that what we research lies in reverse engineering and sketches the main content of this paper. In chapter 2, the basic functions of Test3D are described simply . Then, some basic theories about 3D graphic programming are introduced. Three key techniques are described in chapter 3. They are oriented-object, OpenGL and multithread. In chapter 4, we research a way how to generate curve by discrete points. The way uses several low-order Bezier curve to substitute one high-order Bezier curve in order to avoid computing high-order negative matrix. The curve produced by this way has good smoothness. The chapter 5 studies how to generate feature curve automatically from point-clouds. A technique that searches close points and then gets feature domain by judging the curvature. In chapter 6, we discuss the technique about surface reconstruction and present a simple and effective way. The chapter 7 introduces the basic content of iges and shows how to realize it. We concluded in chapter 8
本论文的第一章对逆向工程进行了简单介绍，说明了本论文研究内容在逆向工程中所处的位置，并简单介绍要重点研究的内容。第二章先简单描述了Test3D软件的基本功能，然后介绍了三维图形编程所需要的一些基本理论。第三章介绍了软件中用到的三项关键技术：面向对象技术、OpenGL以及多线程编程技术。第四章对由离散点构建曲线进行了研究，绕过高阶矩阵求逆，把由k个低阶的Bezier曲线拼合产生的复合曲线来代替单一的高阶Bezier曲线，并保证曲线之间的光滑过渡。第五章研究了如何自动由点云寻找特征点云带。通过寻找邻近点计算曲率，并通过曲率大小得到特征点云带。第六章探讨了由海量散乱点重构曲面的技术，并提出了一种简单高效的曲面重构方法。第七章介绍了IGES接口，并说明如何实现这种接口。第八章对全文进行了总结
3D model reconstruction based on point-clouds in reverse engineering has significant application in many areas. However, measurement system can not link with 3D CAD system directly because the measured dense scattered data can not be processed effectively by 3D CAD software. This is a choke point in reverse engineering. This paper researches and designs a software named Test3D. The following is the main ideas: firstly, it should become the linked part between measurement system and 3D CAD system. Then, it should can reconstruct surface from point-clouds directly in order to output surface model that can be used by CAM software directly.
In this paper, the chapter 1 introduces the concept of reverse engineering, shows the position that what we research lies in reverse engineering and sketches the main content of this paper. In chapter 2, the basic functions of Test3D are described simply . Then, some basic theories about 3D graphic programming are introduced. Three key techniques are described in chapter 3. They are oriented-object, OpenGL and multithread. In chapter 4, we research a way how to generate curve by discrete points. The way uses several low-order Bezier curve to substitute one high-order Bezier curve in order to avoid computing high-order negative matrix. The curve produced by this way has good smoothness. The chapter 5 studies how to generate feature curve automatically from point-clouds. A technique that searches close points and then gets feature domain by judging the curvature. In chapter 6, we discuss the technique about surface reconstruction and present a simple and effective way. The chapter 7 introduces the basic content of iges and shows how to realize it. We concluded in chapter 8
引文
[1] B. Bidanda, Y. A. Hosni. Reverse engineering and its relevance to industrial engineering : a
critical review. Computers ind . Engng , 26(2) , 343~348 ,1994 .
[2] S. Jarzabek, I. Woon. Towards a precise description of reverse engineering methods and tools. Software Maintenance and Reengineering, 1997. EUROMICRO 97. First Euromicro Conference on , 17-19 Mar 1997.
[3] T. Varady , R. Martin, J. Coxt. Reverse engineering of geometric modles-an introduction . Computer-Aided Design , 29 (4) , 255~268 , 1997 .
[4] I. D. Baxter, M. Mehlich. Reverse engineering is reverse forward engineering. Reverse Engineering, 1997. Proceedings of the Fourth Working Conference on , 6-8 Oct 1997.
[5] 张丽艳, 廖文和, 周儒荣. 逆向工程的关键技术及其应用研究. 数据采集与处理 l(14) No. 1 Mar. 1999.
[6] G. Sansoni, M. Carocci, R. Rodella. Calibration and performance evaluation of a 3-D imaging
sensor based on the projection of structured light . IEEE Transactions on Instrumentation and
Measurement, 49 (3) , Jun 2000.
[7] R. Rodella, G. Sansoni. 3D shape recovery and registration based on the projection of
non-coherent structured light. 3-D Digital Imaging and Modeling, 1999. Proceedings. Second
International Conference on , 1999.
[8] L. Biancardi, G. Sansoni, F. Docchio. Adaptive whole-field optical profilometry: a study of t
he systematic errors. IEEE Transactions on Instrumentation and Measurement, 44(1) , Feb
1995.
[9] G. Sansoni, L. Biancardi, F. Docchio, U. Minoni. Comparative analysis of low-pass filters for
the demodulation of projected gratings in 3-D adaptive profilometry. IEEE Transactions on
Instrumentation and Measurement, 43(1 ), Feb 1994.
[10] G. Sansoni, L. Biancardi, U. Minoni, F. Docchio. A novel, adaptive system for 3-D optical
profilometry using a liquid crystal light projector. IEEE Transactions on Instrumentation and
Measurement, 43 (4) , Aug 1994.
[11] H. Hoppe, T. Derose, T. Duchamp, et al. Surface reconstruction from unorganized points.
Proc. SIGGRAPH: 71-78, 1992.
[12] X. Xu, C. Pain, A. J. H, et al. An automatic meshing technique for Delaunay triangulations.
Comput. Methods Appl. Mech. Engrg. 161:297-303, 1998.
[13] H. Weimer, J. Warren. Fast approximating triangulation of large scattered datasets. Advances
in Engrg. Software, 30:389-400, 1999.
[14] K. D. Tamal, G. Joachim, James Hudson. Delaunay based shape reconstruction from large
data. IEEE Proc. Symposium On Parallel- and Large-Data Visualization and Graphics, 19-27,
2001.
[15] C. D. Woodward. Skinning techniques for interactive B-Spline Surfaces interpolation. CAD,
1988,20(8):441-451.
[16] L. Piegl, W.Tiller. Algorithm for approximate nurbs skinning. Computer-Aided Design. 28(9), 699-706 ,1996.
[17] A. L. Marsan, D. Dutta. Computational techniques for automatically tiling and skinning
branched objects. Computers &Graphics. 23(1), February, 1999, pp. 111-126.
[18] L. C. Chen, L in C I. Integrated reverse engineering ap-proach to reconstructing free- form
surfaces. Computer Integrated Manufacturing Systems,1 997,1 0 (1 ):49～6 0.
[19] 吉贝·德芒热. 曲线与曲面的数学. 商务印书馆, 2000.
[20] 孙家广. 计算机图形学(第三版) . 北京: 清华大学出版社, 1998.
[21] 尹希猛, 王运赣, 黄树槐. 快速原型技术—— 90年代新的造型工具. 国机械工程,
1993,4(6).
[22] 毛宽民, 师汉民, 唐小琦, 陈吉红. 激光三维内割技术—一种新型的快速原型技术. 中
国机械工程, 12(5), 2 001.5.
[23] R. C. Luo, Jyh Hwa Tzou, Y. C. Chang. An Internet-based remote control and monitoring
rapid prototyping system. Industrial Electronics Society, 2001. IECON '01. The 27th Annual Conference of the IEEE , Volume: , 2001.
[24] Park Soon-Yong, Lee Yong-Bum, Lee Jong-Min, Chien Sung-Il. 3-D model reconstruction
from three orthogonal views based on merging technique of RP codes. Systems, Man and
Cybernetics, 1995. 'Intelligent Systems for the 21st Century'. IEEE International Conference
on , Volume: 2 , 22-25 Oct 1995.
[25] 郑君立, 达飞鹏, 谭小洪, 雷明涛. OpenGL在逆向工程三维重构中的应用研究. 计算机
应用研究. 2003.1.
[26] 乔林, 费广正, 等. OpenGL程序设计. 北京: 清华大学出版社, 2000.
[27] 白建军, 朱亚平, 等. OpenGL三维图形设计与制作. 北京:人民邮电出版社, 1999.
[28] S. Richard. Jr. Wright. OpenGL SuperBible（2nd Edition. Waite Group Press, 2000.
[29] 谭小洪. 逆向工程中海量离散点三维重构处理及研究. 东南大学硕士论文. 2002.3.
[30] 谭小洪, 达飞鹏, 王丙文, 雷明涛, 郑君立. OOP在图形处理中的应用——三维点云的
处理. 现代电子技术. 2001.12.
[31] Stanley B. Lippman 著. 侯捷 译. 深度探索C＋＋对象模型. 华中科技大学出版社, 2001
[32] 侯俊杰. 深入浅出MFC(2nd). 华中科技大学出版社, 2001.
[33] David J. Kruglinski, Scot Wingo, George Shepherd. VC＋＋6.0技术内幕. 北京希望电子出
版社,1999.
[34] S. William. Operating Systems:Internals and Design Principles 3 rd. Englewood Cliffs,NJ:
Prentice- Hall,1998.
[35] T. Pham, P.Garg. Multithreaded Programming with Windows NT. Englewood Cliffs,NJ:
Prentice- Hall,1996.
[36] Jeffrey Richter 著. 王建华等 译. Windows核心编程. 机械工业出版社, 2000.
[37] 郑尚文, 达飞鹏, 郑君立. 海量数据的特征区域搜索算法研究. 已投计算机辅助设计和
图形学学报.
[38] 周儒荣, 张丽艳, 苏旭, 周来水. 海量散乱点的曲面重建算法研究. 软件学报, 2001, 12(2):249-255.
[39] R. Sacchi, J. F. Poliakoff, P. D. Thomas. Curvature estimation for segmentation of triangu-
lated surfaces. 3-D Digital Imaging and Modeling, 1999:536-543.
[40] P.J. Besl, R.C.Jain. Segmentation through variable-order surface fitting[J]. IEEE Transactions
on Pattern Analysis & Machine Intelligence, 1988,10(2):167-192.
[41] G.Taubin. Estimation of planar curves, surfaces, and nonplanar space curves defined by
implicit equations with applications to edge and range image segmentation. Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(11):1115-1138.
[42] 张丽艳, 周儒荣, 蔡炜斌, 周来水. 海量测量数据简化技术研究. 计算机辅助设计与图形学学报, 2001, 13(11): 1019-1023.
[43] 李磊. 快速并行乘幂法及反乘幂法. 计算数学, 1995, 3:253-259.
[44] B.Guo. Surface reconstruction:from points to spline. Computer Aided Design, 2 9(4),1997.
[45] C. L .Bajaj, F.Bernardini, G.Xu. Automatic reconstruction of surfaces and scalar fields from
3D scans. ComputerGraphics,1995,29(Siggraph' 95).
[46] X.Chen. Surface modeling of range data by constrained triangulation. Computer Aided
Design,1994,26 (3).
[47] H.Fuchs, Z.Kedem, etal. Optimal Surface Reconstruction from Planar Contours, Communi-
cations of the ACM, Vol. 20, 1977.
[48] E. Keppel. Approximating Complex Surface by Triangulation of Contour Lines, IBM J. R&D, Vol. 19, 1975.
[49] D. Meyers, S. Skinner. Surfaces from Contours, ACM Transactions on Graphics, 11(3), 1992.
[50] Barequet, Gill, Daniel Shapiro, Ayellet Tal. History Consideration in Reconstructing Polyhe-
dral Surface from Parallel Slices, Proceeding of Visualization '96, San Francisco, California, Oct. 27 - Nov. 1, 1996.
[51] H. N.Ghristiansen, T. W.Sederberg. Conversion of Complex Contours Line Definition into
Polygonal Element Mosaics, Computer Graphics, 12(2), 1978.
[52] 沈纪桂, 陈廉清. IGES――实现CAD/CAM之间数据交换的规范. 中国机械工程. 9(7),
1998.
[53] 周廷美, 吴云, 王仲范. IGES的数据结构及虚拟原型的生成. 武汉汽车工业大学学报.
2000.2.
critical review. Computers ind . Engng , 26(2) , 343~348 ,1994 .
[2] S. Jarzabek, I. Woon. Towards a precise description of reverse engineering methods and tools. Software Maintenance and Reengineering, 1997. EUROMICRO 97. First Euromicro Conference on , 17-19 Mar 1997.
[3] T. Varady , R. Martin, J. Coxt. Reverse engineering of geometric modles-an introduction . Computer-Aided Design , 29 (4) , 255~268 , 1997 .
[4] I. D. Baxter, M. Mehlich. Reverse engineering is reverse forward engineering. Reverse Engineering, 1997. Proceedings of the Fourth Working Conference on , 6-8 Oct 1997.
[5] 张丽艳, 廖文和, 周儒荣. 逆向工程的关键技术及其应用研究. 数据采集与处理 l(14) No. 1 Mar. 1999.
[6] G. Sansoni, M. Carocci, R. Rodella. Calibration and performance evaluation of a 3-D imaging
sensor based on the projection of structured light . IEEE Transactions on Instrumentation and
Measurement, 49 (3) , Jun 2000.
[7] R. Rodella, G. Sansoni. 3D shape recovery and registration based on the projection of
non-coherent structured light. 3-D Digital Imaging and Modeling, 1999. Proceedings. Second
International Conference on , 1999.
[8] L. Biancardi, G. Sansoni, F. Docchio. Adaptive whole-field optical profilometry: a study of t
he systematic errors. IEEE Transactions on Instrumentation and Measurement, 44(1) , Feb
1995.
[9] G. Sansoni, L. Biancardi, F. Docchio, U. Minoni. Comparative analysis of low-pass filters for
the demodulation of projected gratings in 3-D adaptive profilometry. IEEE Transactions on
Instrumentation and Measurement, 43(1 ), Feb 1994.
[10] G. Sansoni, L. Biancardi, U. Minoni, F. Docchio. A novel, adaptive system for 3-D optical
profilometry using a liquid crystal light projector. IEEE Transactions on Instrumentation and
Measurement, 43 (4) , Aug 1994.
[11] H. Hoppe, T. Derose, T. Duchamp, et al. Surface reconstruction from unorganized points.
Proc. SIGGRAPH: 71-78, 1992.
[12] X. Xu, C. Pain, A. J. H, et al. An automatic meshing technique for Delaunay triangulations.
Comput. Methods Appl. Mech. Engrg. 161:297-303, 1998.
[13] H. Weimer, J. Warren. Fast approximating triangulation of large scattered datasets. Advances
in Engrg. Software, 30:389-400, 1999.
[14] K. D. Tamal, G. Joachim, James Hudson. Delaunay based shape reconstruction from large
data. IEEE Proc. Symposium On Parallel- and Large-Data Visualization and Graphics, 19-27,
2001.
[15] C. D. Woodward. Skinning techniques for interactive B-Spline Surfaces interpolation. CAD,
1988,20(8):441-451.
[16] L. Piegl, W.Tiller. Algorithm for approximate nurbs skinning. Computer-Aided Design. 28(9), 699-706 ,1996.
[17] A. L. Marsan, D. Dutta. Computational techniques for automatically tiling and skinning
branched objects. Computers &Graphics. 23(1), February, 1999, pp. 111-126.
[18] L. C. Chen, L in C I. Integrated reverse engineering ap-proach to reconstructing free- form
surfaces. Computer Integrated Manufacturing Systems,1 997,1 0 (1 ):49～6 0.
[19] 吉贝·德芒热. 曲线与曲面的数学. 商务印书馆, 2000.
[20] 孙家广. 计算机图形学(第三版) . 北京: 清华大学出版社, 1998.
[21] 尹希猛, 王运赣, 黄树槐. 快速原型技术—— 90年代新的造型工具. 国机械工程,
1993,4(6).
[22] 毛宽民, 师汉民, 唐小琦, 陈吉红. 激光三维内割技术—一种新型的快速原型技术. 中
国机械工程, 12(5), 2 001.5.
[23] R. C. Luo, Jyh Hwa Tzou, Y. C. Chang. An Internet-based remote control and monitoring
rapid prototyping system. Industrial Electronics Society, 2001. IECON '01. The 27th Annual Conference of the IEEE , Volume: , 2001.
[24] Park Soon-Yong, Lee Yong-Bum, Lee Jong-Min, Chien Sung-Il. 3-D model reconstruction
from three orthogonal views based on merging technique of RP codes. Systems, Man and
Cybernetics, 1995. 'Intelligent Systems for the 21st Century'. IEEE International Conference
on , Volume: 2 , 22-25 Oct 1995.
[25] 郑君立, 达飞鹏, 谭小洪, 雷明涛. OpenGL在逆向工程三维重构中的应用研究. 计算机
应用研究. 2003.1.
[26] 乔林, 费广正, 等. OpenGL程序设计. 北京: 清华大学出版社, 2000.
[27] 白建军, 朱亚平, 等. OpenGL三维图形设计与制作. 北京:人民邮电出版社, 1999.
[28] S. Richard. Jr. Wright. OpenGL SuperBible（2nd Edition. Waite Group Press, 2000.
[29] 谭小洪. 逆向工程中海量离散点三维重构处理及研究. 东南大学硕士论文. 2002.3.
[30] 谭小洪, 达飞鹏, 王丙文, 雷明涛, 郑君立. OOP在图形处理中的应用——三维点云的
处理. 现代电子技术. 2001.12.
[31] Stanley B. Lippman 著. 侯捷 译. 深度探索C＋＋对象模型. 华中科技大学出版社, 2001
[32] 侯俊杰. 深入浅出MFC(2nd). 华中科技大学出版社, 2001.
[33] David J. Kruglinski, Scot Wingo, George Shepherd. VC＋＋6.0技术内幕. 北京希望电子出
版社,1999.
[34] S. William. Operating Systems:Internals and Design Principles 3 rd. Englewood Cliffs,NJ:
Prentice- Hall,1998.
[35] T. Pham, P.Garg. Multithreaded Programming with Windows NT. Englewood Cliffs,NJ:
Prentice- Hall,1996.
[36] Jeffrey Richter 著. 王建华等 译. Windows核心编程. 机械工业出版社, 2000.
[37] 郑尚文, 达飞鹏, 郑君立. 海量数据的特征区域搜索算法研究. 已投计算机辅助设计和
图形学学报.
[38] 周儒荣, 张丽艳, 苏旭, 周来水. 海量散乱点的曲面重建算法研究. 软件学报, 2001, 12(2):249-255.
[39] R. Sacchi, J. F. Poliakoff, P. D. Thomas. Curvature estimation for segmentation of triangu-
lated surfaces. 3-D Digital Imaging and Modeling, 1999:536-543.
[40] P.J. Besl, R.C.Jain. Segmentation through variable-order surface fitting[J]. IEEE Transactions
on Pattern Analysis & Machine Intelligence, 1988,10(2):167-192.
[41] G.Taubin. Estimation of planar curves, surfaces, and nonplanar space curves defined by
implicit equations with applications to edge and range image segmentation. Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(11):1115-1138.
[42] 张丽艳, 周儒荣, 蔡炜斌, 周来水. 海量测量数据简化技术研究. 计算机辅助设计与图形学学报, 2001, 13(11): 1019-1023.
[43] 李磊. 快速并行乘幂法及反乘幂法. 计算数学, 1995, 3:253-259.
[44] B.Guo. Surface reconstruction:from points to spline. Computer Aided Design, 2 9(4),1997.
[45] C. L .Bajaj, F.Bernardini, G.Xu. Automatic reconstruction of surfaces and scalar fields from
3D scans. ComputerGraphics,1995,29(Siggraph' 95).
[46] X.Chen. Surface modeling of range data by constrained triangulation. Computer Aided
Design,1994,26 (3).
[47] H.Fuchs, Z.Kedem, etal. Optimal Surface Reconstruction from Planar Contours, Communi-
cations of the ACM, Vol. 20, 1977.
[48] E. Keppel. Approximating Complex Surface by Triangulation of Contour Lines, IBM J. R&D, Vol. 19, 1975.
[49] D. Meyers, S. Skinner. Surfaces from Contours, ACM Transactions on Graphics, 11(3), 1992.
[50] Barequet, Gill, Daniel Shapiro, Ayellet Tal. History Consideration in Reconstructing Polyhe-
dral Surface from Parallel Slices, Proceeding of Visualization '96, San Francisco, California, Oct. 27 - Nov. 1, 1996.
[51] H. N.Ghristiansen, T. W.Sederberg. Conversion of Complex Contours Line Definition into
Polygonal Element Mosaics, Computer Graphics, 12(2), 1978.
[52] 沈纪桂, 陈廉清. IGES――实现CAD/CAM之间数据交换的规范. 中国机械工程. 9(7),
1998.
[53] 周廷美, 吴云, 王仲范. IGES的数据结构及虚拟原型的生成. 武汉汽车工业大学学报.
2000.2.