第一章绪论
引言一般产品开发过程是根据市场需要，提出目标和技术指标，进行功能设计，由设计数据构造产品的几何模型，再经过数r}‘加工等一系列的活动产生产品的过程。然}fn在许多情况下，只有产品样件或实物模型，Ifn没有产品的原始设计资料和图纸。为了适应先进制造技术的发展，需要将这些样件或模型还原为CAD模型。这种从实物样件获取产品设计、制造工艺等相关信息的技术，已发展为CAD/CAM中的一个相对独立的范畴，统称为“逆向工程”(ReverseEngineering)目前，关十逆向工程的研究主要集中在几何反求上，即如何从实物或样件上准确高效地采集复杂二维表面数据，进}fn快速地获取其CAD模型。由十测量设备采集的二维表面数据通常比较密集，因Ifn形象地称作点云(pointcloud)，点云数据是二维点坐标(x,y,z)的集合。按照数据的组织形式，点云可分为有序点云和散乱点云。有序点云的重构是指:对给出的采样十已知曲面上的一系列采样点，构造出依次通过或几乎通过这些采样点的曲面，作为原曲面的逼近。
在逆向工程中，由十数据来源的不同造成数据组织形式的不一致，使得到的数据点集并没有一定的组织形式，因此点云数据的重构更多的是无序点云，由十采样密度的足够稠密，无法也无需找到通过所有采样点的曲面，一般只需根据测量获得的点集重构出能反应原始点云形状的面作为重构曲面。逆向工程技术已在许多领域得到应用，例如航空、航天、造船、汽车、模具、医学及考古等。国内外对逆向工程技术都进行了大量的研究。以匈牙利人Varady为首的小组对逆向工程中的数据分块、曲线曲面拟合、曲面过渡、曲面模型的建立等工作进行了研究，Cardiff大学的Martin等和Varady有大量的合作，他们对规则曲面的拟合、约束的识别和添加、B-rep结构的建立等方面进行了研究;Utah大学的Thompson等对约束的添加、基十特征的模型反求、基十知识的逆向工程等进行了研究;Ohio州立大学的Menq等对二坐标测量技术、自由曲线曲面拟合、数据分块等进行了研究;国内研究逆向工程技术的也很多，目前高校研究逆向工程的有南京航空航天大学、浙江大学、上海交通大学、西北工业大学、西安交通大学、北京航空航天大学、华中科技大学等。2逆向工程的基本流程逆向工程的基本流程是:对实物样件进行坐标数据采集，得到表面几何数据:然后对这些数据进行补缺、简化、平滑等预处理:由十测量模型通常由多个面组成，因Ifn需要对测量数据进行分块，再进行曲面重构，在曲面模型的基础上可进一步建立基十B一二p结构的产品CAD模型。图1.1是逆向工程的基本工作流程示意降}「‘」。图1.1逆向工程的基本工作流程逆向工程涉及的内容非常广泛，本文研究的内容主要是其中的曲面模型重构问题。基十测量数据所得点云进行曲面重构是目前计算机降}形学领域所研究的热门问题之一，在实践中，其研究可用十许多领域，如逆向工程、G工S(Geographic工nformationSystem)中的数字高程模型、虚拟现实和医学图像以及文化遗产保护等许多领域。
3曲面重构研究现状在1965年Shepard提出了基十数据的逆距离加权拟合曲面方法，即Shepard}"'法。其基本思想是将插值函数定义为各数据点函数值的加权平均，其权因子与距离成反比。这种方法存在几个缺点，包括在数据点处出现尖点、角点、平坦区域以及受远距离点的不适当影响等，该方法的插值结果只能是CO连续，因为该方法是全局插值算法，所以当增加、删除或修改某数据点时，权函数需要重新计算。1971年，地质工作者Hardy}3」在绘制地形等高线时遇到了散乱数据拟合曲面的问题，他提出了一种新的Multiquadric(M(})径向基函数插值法，他采用的基函数表达式为护IX一X.IIZ+r2，以止匕为基函数来构造曲面的二兀函数，收至。了较好的效果。但这种方法是一种全局函数插值问题，只能应用在数量不太大的情况，例如几百个点的规模，所以很难推广到实际工程应用中。近几年，随着测量设备的口益发展，点云数据规模的增大，专家学者提出了实现点云数据重构的很多方法，Hoppe}n}提出的构造点到物体表面的(有向)距离场，由K近邻
参考文献
[1]刘之生，反求工程技术「M]，北京，机械工业出版社，1996
[2] Shepard D, A two dimensional interpolation function for irregularly spaced data[J]，Proceedings of ACM 23rd National Conference, 1968:571一521
[3] R. L. Hardy, Multiquadric equations of topography and other irregular surfaces[J]，Geophys. Res，1971(76):1905-1915
[2] Hoppe H, Dereose T, Duchamp TH, et al，Surface reconstruction from unorganized points[A]，Computer Graphics S工GGRAPH 92Proc[C]，New York: ACM, 1992: 71-78
[5]Edelsbrunner H,Mucke EP, Three-dimensional alpha shapes[J]，ACM Transaction on Graphics,1992, 13 (1):X13-72
[6]Amentan,Bernm,Kamvyssclism, Anew Voronoi-based surface reconstruction algorithm [A]，Poceeding of S工GGRaPH 98 [C]，Orlando, ACM, 1998:吐15-X122
[7] Blinn J F, A generalization of algebraic surface drawing[A]，ACM Transactions onGraphics,1982，1(3):235-256
[8]杨军，诸昌铃，带噪声的点云数据的隐式曲面重建算法「J}，西南交通大学学报，2008. 2: 29-3}1
[9]刘含波，土听，强文义，RBF隐式曲面的离散数据快速重建「J}，光学精密工程，2008. 2: 338-313
[10]李道伦，卢德唐，孔祥言等，径向基函数网络的隐式曲面方法「J}，计算机辅助设计与图形学学报，2006, 18 (8):1112-1118
[11]黄森，张海朝，普杰信，李超，基于 RBF神经网络的点云数据曲面重建快速算法「J}，计算机应用2008. 2:X169-X172
[12]童伟华，玛玉瑜，陈发来，基于隐式T样条的曲面重构算法「J}，计算机辅助设计与图形学学报，2006年第3期:358-361
[13] ht却://www. fftw. org
[12]Lorensen WE, et al, Marching cubes:a high resolution 3D surface constructionalgorithm[J]，Computer Graphics, 1987, 21(2):163-169
[15]Boissonnat J-D, Geometric structures for three-dimensional shape representation[J]，ACM Transactions on Graphics，1982, 3(2):266-286
[16] Shen C，0’Brien J，Shewchuk J，工nterpolating and approximating implicit surfacefrom polygon soup[J]，TOG (S工GGRAPH’02) 23 (2002):896-901
[17]Carr J C, Beatson R K, Cherrie J B, et al，Reconstruction and representation of 3Dobjects with radial basis functions [C]，Proceeding of ACM S工GGRAPH 2001, Los Angeles,2001:67-76
[18] Ohtake Y, Belyaev A, Alexa M, et al，Multi一level partition of unity implicits[C]，Computer Graphics Proceeding, Annual Conference Series, ACM S工GGRAPH 2003, SanDiego, 2003:X163-X170
[19]Ohtake Y, Belyaev A, Seidel H P, A multi一scale approach to 3D scattered datainterpolation with compactly supported basis functions[C]，Proceeding of Shape Modeling工nternational,
[20]Turk G, Dinh H Q, 0' Brien J, et al工mplicit surfaces that interpolate[C]，Proceeding
摘要 4-5
ABSTRACT 5-6
第一章 绪论 9-14
1.1 引言 9-10
1.2 逆向工程的基本流程 10
1.3 曲面重构研究现状 10-11
1.4 本文的选题背景和研究内容 11-12
1.5 本文的组织方式 12-14
第二章 点云数据的重构技术和面绘制方法 14-20
2.1 几种常见的重构方法 14-16
2.1.1 Boissoant 方法 14
2.1.2 Hoppe 方法 14-15
2.1.3 径向基函数方法 15
2.1.4 基于隐式T 样条的曲面重构算法 15-16
2.2 面绘制方法 16-18
2.2.1 基于等值线的生成方法 16-17
2.2.2 基于体素（Voxel）的生成方法 17-18
2.2.3 基于能量函数的封闭等值面生成方法 18
2.3 MARCHING CUBE 算法 18-20
第三章 点云数据预处理 20-23
3.1 点云数据重构和插值问题 20
3.2 离面约束点的类型 20-22
3.3 法向量的确定 22-23
3.3.1 微切平面法向量选取 22
3.3.2 法向一致化 22-23
第四章 基于泊松方程实现点云的重构 23-32
4.1 表面重构数学模型 23
4.2 泊松方程 23-24
4.3 泊松方程重构 24-32
4.3.1 理论基础 24-26
4.3.2 数据形式的表示 26-28
4.3.3 定义空间函数，创建向量场 28
4.3.4 方程组求解 28-29
4.3.5 提取等值面 29-30
4.3.6 算法实例 30-32
第五章 基于FFTW 实现点云的重构 32-41
5.1 引言 32-35
5.1.1 复型变换 33-34
5.1.2 实型变换 34-35
5.2 FFTW 函数库的安装方法 35
5.3 基于FFTW 实现点云数据的表面重构 35-39
5.3.1 算法的理论基础 35-36
5.3.2 基于FFTW 实现重构的算法过程 36-38
5.3.3 非均匀采样 38-39
5.4 算法实例 39-41
第六章 总结与展望 41-43
6.1 全文工作总结 41
6.2 后继工作展望 41-43
参考文献 43-46
致谢 46-47
