（控制理论与控制工程专业论文）基于离散点云的三维重建研究与实现.pdf

- - 二， f ，一 。 c l a s s i f i e di n d e x ： u d c ： l i i ii iiiii i iii iiii iiil y 18 0 8 4 0 6 ad is s e r t a t i o nf o r t h ed e g r e eo fm e n g r e s e a r c ha n dr e a l i z a t i o no f t h r e ed i m e n s i o n a lr e c o n s t r u c t i o nbasedlh r e e - d l m e n s l o n c 1 0 na s e o nd i s c r e t ep o i n tc l o u dd a t a c a n d i d a t e ：z h a n gt a o s u p e r v i s o r ：p r o f e s s o ry ex i u f e n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o n t r o lt h e o r ya n dc o n t r o le n g i n e e r i n g d a t eo fs u b m is s i o n ：d e c e m b e r ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 。 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：雅溯 日期：加f p 年乡月x 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 曰在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( - 签- 7 - - ) ：强诱导师( 签字) ：# 毵旁 日期：砂f o 年- 5 月葛日2 0 lo 年了月g 曰 一 l - ， 、 q - 哈尔滨工程大学硕士学位论文 目录 第1 章绪论l 1 1 课题研究的背景与研究意义1 1 2 三维重建系统的国内外研究现状2 1 3 本文基于离散点云的三维重建的流程“4 1 4 论文的主要工作和论文的组织结构5 第2 章基于点云的数据预处理与显示7 2 1 常见的基于点云的数据处理方法总结7 2 2 基于点云的数据处理与三维重建的软件开发环境8 2 2 1 三维图形开发平台的选择8 2 2 2 基于d i r e c t x 软件开发环境的接口的创建9 2 3 点云的三维空间坐标变换方法研究1 0 2 3 1 点云的平移变换1 1 2 3 2 点云的缩放变换1 4 2 3 3 点云的旋转变换15 2 4 基于v c + d i r e c t x 软件平台的点云显示1 8 2 4 1 三维点云数据装载1 8 2 4 2 三维点云的显示及分析2 l 2 5 本章小结2 3 第3 章基于复杂点云的空间三角化与三维剪裁2 5 3 1 引言2 5 3 2 点云的三角化2 5 3 2 。1v o r o n o i 图的确定2 6 3 2 2d e l a u n a y 三角化2 7 3 3 三角化算法的优化设计2 8 3 3 1d e l a u n a y 三角化的算法设计2 8 3 3 2 三角化数据的存储结构的实现3 4 3 3 3 算法实现注意的几个问题3 5 哈尔滨工程大学硕士学位论文 3 4 三维剪裁3 5 3 4 1 剪裁和透视投影3 5 3 4 2 视口变换和像素的显示4 2 3 5 本章小结4 4 第4 章基于网格的渲染技术4 6 4 1 引言4 6 4 2 材质和光照处理4 6 4 2 1 颜色结构体的确定4 6 4 2 2 光源设置的选择4 7 4 2 3 材质设置4 8 4 2 4 顶点的法向量的计算4 8 4 3 纹理映射4 9 4 3 1 顶点纹理坐标的确定”：o 0 4 9 4 3 2 纹理对象的创建5 0 4 3 3 纹理过滤技术的选取51 4 3 4 纹理地址模式的应用5 2 4 4 基于三角化网格渲染的实验结果5 6 4 4 本章小结5 8 第5 章三维重建系统平台的建立5 9 5 1 三维复杂点云的数据格式的确定与存储5 9 5 2 三维网格数据文件基本格式的确定6 1 5 2 1 模板的概述6 1 5 2 2 三维网格数据文件的场景主框架建立6 2 5 2 3 主框架下的子框架建立6 3 5 - 3 三维网格数据文件的数据加载6 4 5 4 网格数据的处理6 5 5 5 网格数据的优化6 6 5 6 基于复杂点云的三维重建结果及分析6 8 5 7 本章小结7 1 结论7 2 o 哈尔滨丁程大学硕士学位论文 j m ；i；i ；高i i ；i ；i i i i ；i ；i ；i i i i ；i ；i i 宣 参考文献7 4 攻读硕士学位期间发表的论文和取得的科研成果7 9 致谢8 0 哈尔滨工程大学硕+ 学位论文 摘要 随着深度摄像、激光测距、c t 、m i r 等三维测量和信息获取技术的发展， 包含被测物体表面的离散数据获取成为可能。因此，基于离散数据的三维重 建成为了人工智能领域研究的重点，其应用领域十分广泛。 离散数据常以点云的形式出现。传统的基于点云的三维重建方法都是根 据物体表面所具有的某种特征而设计的，通常都具有一定的局限性。因此， 本文主要研究基于简单点云与复杂点云的通用的三维重建方法。 论文首先对三维点云数据在v c + d i r e c t x 平台下进行数据预处理，并将 简单点云直接在平台上显示，从而实现了基于简单点云的三维重建。 然后，对基于复杂点云的空间三角化与三维剪裁进行研究，提出一种复 杂点云的改进的三角化算法，弥补传统算法中当点集存在非凸部分或内环时 三角剖分容易出错的不足，也避免出现两三角片“共圆 现象而导致只删除 其中的一个三角片导致三角化结果出错的缺陷，使得处理后的空间网格反映 出物体表面离散点间的拓扑连接关系，从而有效地揭示离散点云所表现的重 建物体表面的形状，这也是三维重建的关键步骤。 另外，为了重建出更加逼真的物体，还进一步使用基于网格的渲染技术， 即对空间三角网格增加光照和材质处理以及纹理映射，大大提高了渲染速度， 改善了渲染效果。 最后，综合以上几个步骤搭建三维系统平台，提出一种基于复杂点云三 维重建的数据格式。同时，基于此开发平台提出一种用于存储三维重建数据 的框架结构，利用这种结构创建三维网格数据文件，从而在平台上加载该文 件完成三维重建。本文针对两种不同的点云分别进行了三维重建实验。实验 结果表明，本文所提出的三维重建方法适合重建现实世界中的大部分物体， 与传统的三维重建方法比起来更具有普遍性，实现简单、成本消耗低、重建 精度高，具有较强的实用性。 关键词：离散点云；数据预处理；三角化：纹理映射；三维重建 ， w i t ht h ed e v e l o p m e n to fd e p t hc a m e r a ，l a s e rr a n g i n g ，c t , m i ra n do t h e r so f t h r e e d i m e n s i o n a lm e a s u r e m e n t sa n di n f o r m a t i o na c q u i r i n gt e c h n o l o g y , i ti s p o s s i b l e t oi n c l u d em u c hi n f o r m a t i o na b o u td i s c r e t ed a t ao fm e a s u r e do b j e c t s u r f a c e t h e r e f o r e ，t h r e e d i m e n s i o n a lr e c o n s t r u c t i o nb a s e do nd i s c r e t ed a t ah a s b e c o m et h ef o c u so fr e s e a r c hi nt h ef i e l do fa r t i f i c i a li n t e l l i g e n c ea n di th a sw i d e r a n g eo fa p p l i c a t i o n s d i s c r e t e d a t ao f t e na p p e a r si nt h ef o r mo fp o i n tc l o u d t h et r a d i t i o n a l t h r e e d i m e n s i o n a lr e c o n s t r u c t i o nm e t h o d sa r eb a s e do nt h eo b je c ts u r f a c eo f c e r t a i nc h a r a c t e r i s t i c sw h i c hh a v e b e e nd e s i g n e d ，t h o s eu s u a l l yh a v es o m e l i m i t a t i o n s s o t h i st h e s i sd i s c u s s e st h r e e d i m e n s i o n a lr e c o n s t r u c t i o nc o n 2 m o n m e t h o d sb a s e do ns i m p l ep o i n tc l o u da n dc o m p l e xp o i n tc l o u d f i r s t ，t h i st h e s i sp r e p r o c e s s e sd a t ao ft h r e ed i m e n s i o n a lp o i n tc l o u da n d d i s p l a y sd i r e c t l ys i m p l ep o i n tc l o u di nt h ev c + d i r e c t xp l a t f o r m ，t h u sa c h i e v e s t h r e e d i m e n s i o n a lr e c o n s t r u c t i o nb a s e do ns i m p l ep o i n tc l o u d t h e nt h i st h e s i s r e s e a r c h e st r i a n g u l a t i o na n dt h r e e d i m e n s i o n a lc u ti nt h es p a c eb a s e do nc o m p l e x p o i n tc l o u d a ni m p r o v e dt r i a n g u l a t i o na l g o r i t h mt oc o m p l e m e n tt h ed r a w b a c k s o ft r a d i t i o n a la l g o r i t h mi sp r o p o s e dw h e nt h e r ei san o n c o n v e xs e to fp o i n t s ，o r i n n e rr i n g s ，t h ep r o b a b i l i t yo ft r i a n g u l a t i o ni se a s yt oc a u s ee r r o r s ，a sw e l la st o a v o i dap h e n o m e n o no ft h et w ot r i a n g u l a rp i e c e sw i t h ”t o t a lc i r c l e ”，c a u s e db yj u s t d e l e t i n gt h eo n eo ft h e m ，a n dt h e nr e f l e c t s t h et o p o l o g i c a lc o n n e c t i o n sa m o n g d i s c r e t ep o i n t so fo b j e c ts u r f a c e t h ep r o p o s e da p p r o a c hr e v e a l se f f e c t i v e l y s u r f a c eo ft h es h a p ew i t hd i s c r e t ed a t a i na d d i t i o n ，t or e b u i l dav i v i do b je c t ，t h i st h e s i sa l s od i s c u s s e st h er e n d e r i n g t e c h n o l o g yb a s e do nt h eg r i d ，n a m e l y , t oa d dl i g h t i n ga n dm a t e r i a l sp r o c e s s i n g ， a n dt e x t u r em a p p i n gt ot r i a n g u l a rm e s h ，w h i c hc a ni m p r o v et h er e n d e r i n gs p e e d a n dr e n d e r i n ge f f e c t sg r e a t l y f i n a l l y , a f t e rt h ec o m b i n a t i o no ft h ea b o v es t e p s ，t h i st h e s i se s t a b l i s h e sa 哈尔溟工程大学硕士学位论文 i i s y s t e mp l a t f o r m an e wd a t af o r m a tb a s e do nc o m p l e xp o i n tc l o u da n dad a t a f r a m es t r u c t u r ei nt e r m so fd e v e l o p e dp l a t f o r ma r ep r o p o s e d ，w h i c hi su s e dt o s t o r e t h ed a t ao ft h r e e d i m e n s i o n a lr e c o n s t r u c t i o n c o r r e s p o n d i n g l y , t h r e e - d i m e n s i o n a l 鲥dd a t af i l e i se s t a b l i s h e da n dl o a d e di nv c + d i r e c t x p l a t f o r m f i n a l l y , t h r e e d i m e n s i o n a lr e c o n s t r u c t i o ne x p e r i m e n t so ft w od i f f e r e n t k i n d so fp o i n tc l o u da r ec a r r i e do u t t h ee x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h e p r o p o s e dm e t h o di ss u i t a b l ef o rm o s to b j e c t sa n di su n i v e r s a l ，s i m p l e ，l o wc o s t ， h i 曲p r e c i s i o n ，s t r o n g l yp r a c t i c a lu s e f u l n e s s ，c o m p a r e d w i t ht r a d i t i o n a l t h r e e d i m e n s i o n a 】r e c o n s t r u c t i o nm e t h o d s k e yw o r d s ：d i s c r e t ep o i n tc l o u dd a t a ；d a t ap r e p r o c e s s ；t r i a n g u l a t i o n ；t e x t u r e m a p p i n g ；t h r e e d i m e n s i o n a lr e c o n s t r u c t i o n 获取真实物体的三维模型，也称三维重建1 。一直是计算机视觉、机器 人学、计算机图形学等领域的一个重要研究课趔列p 4 1 。重建的任务就是利用 多媒体技术，将从传感器或者其他设备获得的采样数据重新恢复物体的三维 结构和物体的原型。它在机器人视觉导航中的障碍物检测p 儿引、文物的数字化 保护眄1 、城市设计规划与管型”、三维地形重建译1 、工业制造中的实物造型卅、 医学影像分析0 1 、虚拟现实”等领域中有着广泛的应用。就文物遗产保护来 说，很多历史文物和遗产由于年代的久远，已经难以保存，再加上现代社会 人类对历史文物的不断破坏，这些遗产遭受的破坏程度与日俱增，于是利用 先进的技术来保护这些宝贵的遗产便成为了十分紧迫的全球性问题，特别是 对于我国这样一个具有历史悠久的文物大国，对遗产的保护将具有更为深远 的意义。再如在城市设计规划与管理中，我们可以预先通过对城市的场景进 行建模，即利用获取的三维数据建立相应的虚拟环境模型，从而展现一个逼 真的三维空间世界。鉴于三维重建具有广泛的应用价值，这就迫使人们寻求 一种手段来获取一个真实物体的三维模型，并能够根据不同方位实时的进行 三维显示。 三维重建的基础就是获取离散的三维数据，也称为离散的三维点型1 2 1 。 目前基于三维数据获取的研究与设计有很多，例如通过激光扫描测距、通 过三维扫描仪1 等先进成熟等技术可以轻松地获取到三维数据。不同的领域 采用不同的设备，所获得的数据结构也不同，重建的目标一样，因此造成重 建方法的多样性。因此，对得到的离散点云进行数据预处理以及使用比较普 遍的方法来重建三维模型，便成为了三维重建的难点。 在对点云进行数据预处理的时候，我们通常进行的是对点云数据进行滤 波、去噪等处理。然而，随着三维重建技术的不断发展，一个突出的难点就 是如何将现有的数据结构经过改进从而建立起一个新的数据结构来表示空间 物体的三维点云数据，使得此数据结构能够表达更多的三维重建信息，从而 有利于后续的三维重建。 哈尔滨- t 程大学硕士学位论文 离散数据的三维重建的另一个难点在于，如何在数据点集中自动地得到 邻近点间正确的拓扑连接关系。而正确的拓扑连接关系将有效地揭示离散数 据集所蕴涵的原始物体表面的形状和拓扑结构引。根据数据点集组织形式的 不同，可以把离散数据点集分成3 类，即点与点之间毫无内在联系的数据点 集称为无组织数据集，第2 类主要来自于医学图像，称为轮廓线或体数据， 数据点呈层状分布，每一层代表物体的一个剖面：第3 类是深度离散数据， 主要由三维激光扫描仪测距技术等硬件采集设备所获得。本文正是基于第3 类的离散数据点集进行三维重构。 在研究如何对三维点云进行三维模型重建的时候，相关的文献资料所阐 述的三维重建技术大部分都是基于物体表面的离散点云具有某类特征或者某 类物体表面而独立设计的三维重建方法4 “哪6 1 ，因此这些三维重建方法都不具 有普遍性，各自都有一定的局限性。例如，有基于规则与不规则建筑物三维 建模方法的研究1 7 川引、有基于规则物体表面的三维重建研究m m q 忙忙2 1 等。因此 这就在我们实际的应用有了很大的局限性，随之所产生的三维重建系统平台 也就只能适应于某种需要而进行单独设计。 本文将点云重建工作分为两大类：一种是基于简单点云的三维重建，另 一种是基于复杂点云的三维重建。寻求一种普遍的不带有局限性的三维点云 的重建方法是当前的迫切工作。本文正是基于此进行研究，即重点研究基于 离散点云的三维重建。 1 2 三维重建系统的国内外研究现状 以三维重建为研究目标的研究方法，在三十多年的发展中，逐渐形成了 各种各样的方法和理论b 3 “驯口5 1 ，然而针对基于离散的三维点云进行三维重建的 研究还不是很多，并且三维重建的流程也不拘一格，大体上可以分成数据预 处理、三角化、纹理渲染等步骤。 数据预处理是三维重建的第一步，因此处理的结果会直接影响后续的三 维重建效果。国内外关于数据预处理的常用处理方法有：数据清理、数据集 成、数据变换、数据优化等。数据清理目前主要是针对于经过硬件采集设备 而获得的三维数据，因为这些采集点会根据采集设备的精度和被测对象表面 的材质等情况，会不可避免地含有噪声点。针对数据清理，目前常用的处理 2 哈尔滨t 程大学硕士学位论文 手段包括采用标准高斯、平均或中值滤波等算法”1 。高斯滤波器在指定域内 的权重为高斯分布，其平均效果较小，故在滤波的同时能较好地保持原数据 的形貌。平均滤波器是利用滤波窗口内各采样数据点的统计平均值来代替当 前点。中值滤波是一种有效的非线性滤波，常用于消除随机脉冲噪声。数据 集成对所得到的所有三维数据进行数据集拼接，然后在统一的坐标系里表示 所有的数据。它是数据预处理研究的比较热门的一个方向，吸引了很多人的 研究兴趣和工作。在这2 0 多年中，通过前人的研究先后形成了一系列关于数 据集成的理论算法，其中包括利用单位四元组进行基于对应三维点集的最小 平方最小化方法口6 1 、不需要特征抽取的任意形状的空间曲线的匹配算法口丌、 与最小平方s v d 对准相结合的方法b 引、基于区域分割的对准算法口9 1 、基于i p c 算法的数据配剧如1 等。数据预处理中的数据变换和数据优化这两个处理操作， 在国内外的研究相对较少，目前针对数据变换和数据优化还没有一种成熟而 统一的理论。 最近几十年来，平面离散的点云的三角网格化p u p 引口习( t r i a u l g u l a t i o n ) 一直是 人们所探究的问题之一。三角网格化又称为三角剖分p 4 “ “圳。三角网格化在许 多领域都有着广泛的应用。例如，在有限元分析中，它是有限元网格生成的 有效途径之一；在计算机辅助设计中，它可以简化几何模型和实体模型的数 据结构以及内部表示；在地理学中，它可以快速生成地理模型睁“3 7 1 。三角网格 化问题可以追溯到1 9 0 7 年，g v o r o n a l 首先提出这个问题，后来d e l a u n a y 在1 9 3 2 年首次提出解决这一问题完整而实用的方法。当今，人们对这个问题 的思考依然是有增无减，国内外关于三角网格化算法本身以及它在各方面的 应用的文章还在不断出现，其中包括比较成熟的方法有：d e l a u n a y 三角剖分 方法( d t ) 3 引和贪心算法( g t ) n3 1 。另外，f o u r i e r 通过任意多边形的梯形剖分、 半单调多边形的构造与三角剖分提出了任意多边形的三角剖分方法p 9 4 川等。 然而这些方法在实现的过程中都有各自的局限性，因此会导致三角剖分的结 果出错。并且国内关于这方面的研究还为数不多，因此开展这方面的研究是 很有必要的。 在整个三维模型重建体系中，单一三维网格模型的渲染是个极其重要的 环节，同时随着三维动画这个新兴领域的崛起，基于三维网格渲染也逐渐成 为了研究热点。目前基于三维物体的渲染主要有光照渲染、纹理渲染，并且 哈尔滨二r 程大学硕士学1 _ 7 = 论文 已经成功地应用到了三维动画领域中，随着人们不断地追求更加逼真的三维 重建效果，材质渲染逐步成为了三维网格渲染的一个重要步骤。 1 3 本文基于离散点云的三维重建的流程 本文设计了基于三维离散点云的三维重建的流程，其核心思想就是几何 重建从拓扑重建获得的三角网格出发，重建带有材质、光照、纹理效果的表 面以近似地再现真实物体的表面。流程具体包括以下三个部分：数据预处理， 离散点云的三角化( 构建三角网格模型) 以及三角网格的渲染。其流程图如 1 1 所示。 三维离散点云 数据预处理 上待重建的： 离散点云三角化 l三维网格 三维网格渲染 经过渲染的三维物体 图1 1 基于三维离散点云的三维重建系统流程图 1 、数据预处理4 1 “蚓 数据预处理是三维重建技术的基础。这里提到的数据，实际上是指我们 预先得到的三维离散数据，我们称之为原始三维离散点云，每个数据均具有 ( z ，y ，z ) 的形式。为了能使重建后的三维物体进行全方位的可视化，就需要初 期对三维点云进行旋转平移等三维坐标变换。 2 、离散点云的三角化 通常得到的三维数据一般都是离散、复杂的三维点云，因此直接显示在 屏幕上，无法得到重建物体的表面。因此需要对点云进行三角化，也称为拓 扑重建，其目的是重建各个离散点之间的拓扑关系，重建结果为一张与原物 4 哈尔滨t 程大学硕士学位论文 体表面拓扑等价的三角形网格。本文为了三角化实现方便，采用的是先将三 维数据投影到平面上，然后进行二维三角化，最后在已形成的平面三角网格 中的每个顶点上加入深度坐标，即通过二维三角割分到三维空间的映射。这 样的三角化网格可以很好的再现出真实物体的表面。 3 、三维网格的渲染一副 经过前面的过程可以得到真实物体的三角网格，它们通常已经能够正确 反映出离散点间的拓扑关系。但为了再现出真实物体的表面，就需要模仿真 实场景进行光照处理，对三角化网格的各个顶点赋予颜色信息和材质信息， 从而绘制成具有真实感色彩的三维模型。其中纹理映射可以分为两种方法： 一种是将拍摄到实物的一系列彩色照片映射到几何模型上，这个过程称为纹 理贴图1 ，也就是要解决一个由照片到几何模型的映射问题p 5 1 ；另一种是在 获取三维数据时，即获取每个点的几何信息的同时，获取点云的颜色信息， 从而生成真实感的三维模型。 1 4 论文的主要工作和论文的组织结构 针对当前一些相对比较成熟的三维重建技术，并结合相关课题，本文对 基于三维离散点云的三维重建技术展开了系统的研究。 首先对三维点云进行数据预处理，即三维点云的旋转变换、三维数据结 构的优化。然后对预处理后的数据在v c + d i r e c t x 平台下进行显示。由于基 于简单的点云在平台下已经能够准确显示出三维模型，因此针对于简单点云 的重建工作就结束了。 当然，更多的三维物体表面是复杂的，不可能通过点云数据直接重建出 其三维模型，因此需要进一步地处理。对于经过预处理的点云数据，如何以 这些数据点为基础重建其三维模型，这是三维重建的关键技术之一，也是难 点所在。处理此问题的常用方法就是需要进行三角化，也称三角剖分。在这 方面己经有很多研究人员做了大量的工作，目前已有一些生成三维表面网格 模型的自动重建算法，但还没有公认的最好的办法。因此本文将根据已有的 三角化算法进行改进，尽可能使经过三角化处理的三角网格最优化。 最后为了能生成更逼真的三维模型，我们对被剖分的空间三角网格采用 了纹理映射( 纹理贴图) 技术来渲染网格表面，从而达到更加真实的三维重 哈尔滨工程大学硕士学位论文 建效果。 、 本文主要分为5 章，具体安排如下： 第1 章是绪论部分，介绍了课题的研究背景与研究意义、阐述了国内外 三维重建流程中数据预处理、点云三角化、三维网格渲染的研究现状，并给 出本文基于离散点云的三维重建流程。 第2 章是基于点云的数据预处理与显示，总结了点云常用的数据预处理 方法，并对点云进行了坐标变换的预处理，最后通过两组实验对预处理后的 点云在v c + d i r e c tx 平台下进行显示。 第3 章研究基于复杂点云的空间三角化与三维剪裁，重点研究对预处理 后的三维数据点进行三角化。通过对比几种常用的三角化算法的优缺点，将 三角化算法进行改进，并给出改进后算法的实验结果及分析。 第4 章主要研究基于空间网格的渲染，经过三角剖分后的空间网格虽然 可以显示三维物体表面轮廓，但为了更加逼真地显示三维物体，还需要进行 空间网格的渲染。为此，本章将详细介绍材质和光照设置、纹理映射三个纹 理渲染的步骤，还结合几个实例给出不同的渲染效果并做了对比。 第5 章将建立三维重建系统平台，重点介绍三维网格数据文件的写入、 读取及其优化，从而搭建出三维重建系统的软件平台，并根据前几章所作的 工作，以及基于v c + d i r e c tx 平台下所提供的a p i 函数，完整地实现几个三 维模型实例的重建工作流程。 论文的最后对全文进行系统总结，并根据现有的研究进展对未来进行展 望。 6 哈尔滨工程大学硕士学位论文 第2 章基于点云的数据预处理与显示 通过绪论的介绍可知：数据预处理中数据变换在国内外研究还不够成熟， 为此本章将对数据预处理中的数据变换方法进重点研究，通过实验来验证本 章所给出的方法的可行性。 点云的数据预处理是进行三维重建的基础，也是三维重建流程的重要步 骤，其主要有以下几个原因： 1 、通常三维数据是通过激光测距仪、三维坐标仪等硬件设备采集而得到 的，由于在采集过程中会不可避免地受到外界的各种干扰，所以往往会出现 数据冗余、数据空缺等现象，因此进行数据预处理是很有必要的，它保证了 后续三维重建的逼真效果。 2 、由于三维重建的实时性和重建效果与所提供的数据结构有很大的关 系，因此对数据结构的优化是至关重要的一步，它同样是数据预处理当中的 难点之一。 3 、由于对整个物体表面进行三维重建，因此为了从不同方位显示重建后 的三维物体，就必须预先对点云数据进行三维坐标变换，即数据变换。 本章主要针对基于点云的预处理来进行研究，将首先给出三维图形开发 平台的选择及其接口，然后，重点给出点云的三维坐标变换，并在点云的处 理平台上对预处理后的三维点云进行显示，最后对所给出显示结果进行分析。 2 1 常见的基于点云的数据处理方法总结 一般来讲，数据预处理并没有统一的标准，只能说是根据不同类型的分 析数据和功能需求，在对数据内容与特性做了充分的理解之后，再选择相关 的数据预处理技术。通常会结合多种预处理技术。常见的预处理技术有m ： 数据清理、数据集成、数据变换、数据优化等。下面分别加以介绍： 1 、数据清理 现实世界的数据一般是不完整的、含有噪声的和不一致的。数据清理主 要完成填充空缺值，识别孤立点，消除噪声和干扰，并校正数据中的不一致。 2 、数据集成 7 哈尔滨丁程大学硕士学位论文 实际需要重建的三维图像通常需要来自多个数据源，然后不同的数据源 包含着不同的数据信息，为此必须进行数据集成，使多个数据源达成统一。 3 、数据变换 这里有两层含义，一层含义是对数据格式本身的变换。来自不同数据源 一的数据由于包含了不同的数据信息，所以也可能存在数据格式定义上的差异， 或者存在因数据过于冗余而无法确定有效数据信息的情形。此时便需要将数 - 据转换为统一的形式，并且适合后续处理的有效形式。另外一层含义是对数 据坐标的变换，即需要对获取到的三维数据的坐标进行变换，常见的坐标变 换有：平移变换、放大缩小变换、旋转变换等。 4 、数据优化 利用c c + + 语言中的结构体，并根据易于存储和理解分析数据信息的特 点，构造出新的结构体，这样既可以有效地减少数据存储空间，又可以使下 一步的数据处理更有效。 通过以上几种数据预处理方法，通常就可以建立起有效的数据结构来精 确地描述其散乱点云的数据结构，从而为后续的三维重建工作打下基础。 2 2 基于点云的数据处理与三维重建的软件开发环境 通常我们获取到的原始数据源是大量的三维点云，所以为了能够在计算 机屏幕上显示三维图像，即重建出三维物体，必须有一个三维处理环境的平 台。本文采用d i r e c t x 作为点云的处理环境与软件开发平台。 2 2 1 三维图形开发平台的选择 d i r e c t x 和o p e n g l 是近些年发展起来的两个性能卓越的三维图形标准一u p 8 1 。虽然o p e n g l 是一种立即模式的3 da p i ，在实时三维( 3 d ) 处理中性能突 。出，但是o p e n g l 立即模式不允许o p e n g l 将本帧画面的图形信息传送给下 一帧画面，必须进行实时重绘，这在一定程度上造成了系统资源的浪费。相 比之下，d i r e c t x 是一种保留模式的3 da p i ，在保证实时性的要求下可以大 量地节省系统资源，因此它很好地兼顾了实时性和节省系统资源两个方面。 d i r e c t x 是一种应用程序接口，它可让以w i n d o w s 为平台的程序获得更 高的执行效率，加强3 d 图形和声音效果，并提供设计人员一个共同的硬件 渲染的软件接口，调用这些接口的函数，就可以省去三维图形的重复开发。 并且d i r e c t x 还得到了硬件加速的支持，因此使用d i r e c t x 平台可以充分利用 其提供的在3 d 图形方面表现地优越性。 通常d i r e c t x 与m i c r o s o f tv i s u a lc + + 相结合构成完整的三维重建的开发 环境平台，因此，利用此平台可以使我们真正地实现高品质、交互式的三维 图像处理以及三维重建。 2 2 2 基于d i r e c t x 软件开发环境的接口的创建 基于d i r e c t x 作为本设计的软件开发平台的一个主要目的是因为d i r e c t x 里面提供了d i r e c tg r a p h i c s 组件接口，其接口里面提供了大量的a p i 接口函 数，用来实现数据预处理、数据显示等功能。而且该组件是直接与硬件驱动 程序打交道，因此在进行相关功能的实现实时性很高。 首先要创建一个用来访问该组件的接口对象，再创建一个d i r e c t 3 d 设备， 然后利用d i r e c t 3 d 设备的接口方法去操纵管道流水线进行离散点云的数据预 哈尔滨工程大学硕士学位论文 处理、三维空间网格的渲染以及三维重建。下面通过流程图2 1 来阐述接口 的创建步骤。 图2 1 基于d i r e c t x 软件开发环境的接口的创建流程图 2 3 点云的三维空间坐标变换方法研究 为了将散乱的三维点云进行任意视角进行显示，就需要实现对点云的分 割、平移、缩放、旋转、滤除干扰点等一系列的处理，其实质就是对点云进 行三维坐标的变换9 1 。对点云数据进行三维坐标变换包括：平移变换、旋转 变换和放大缩放变换等。 1 0 坐 1 、 坐标系 2 、 的坐标 两 建立摄 维的图 转换， 景中移 以上的 得到的 对物体 三维旋转的扩展则不是那么简单。在讨论砂平面上的二维旋转时，只需要考 虑沿着垂直于砂平面的坐标轴进行旋转就可以了，而在三维空间中，可能选 择空间任意方向作为旋转轴方向，大多数处理方法是将三维旋转作为绕三个 坐标轴的二维旋转的复合进行处理：另外一种解决方案则是指定轴的方向和 旋转角度建立一个总的旋转矩阵，因为任意次序的变换均可通过将序列中的 每个变换矩阵合并起来形成一个矩阵。 2 3 1 点云的平移变换 点云的平移的目的就是把点云移动到屏幕的最佳位置，便于观察，或者 把没有显示在屏幕上的点云通过平移的方法让它显示出来。点云的平移是三 维图形平移变换的应用。， 考虑某一坐标系x y z 下的任意一点p = ( 只，只，) ，坐标系中任选一点 0 = ( d ，0 ，0 。：) ，建立一个新的坐标系x y z ，x y z 。各坐标轴正向平行于x y z 轴。现在需要求出点p 在新坐标系x y z 下的坐标p = ( 尸，尸，p ：) 。 如图2 2 所示，由空间几何的向量性质得知： 0 0 + 0 p ：o p y o 图2 2 平移坐标变换 从而，展开向量的坐标分量取得如下的方程式： 于是，d + p = p ，p = p 一0 。 由此可以看到，坐标系x y z 可看成是坐标系x y z 平行移动而来的，其中 x 轴方向平移0 。单位，y 轴方向平移d ，单位，z 轴方向平移0 ：单位。在这 种坐标系平移变换下，点的坐标变换是将相应的x 、y 、z 坐标值减去对应的 平移长度而得到的。 为此，先将点p = ( 只，只，) 与一个四维向量( e ，1 ) 一一对应起来， 然后，可根据p = p 一0 等式建立等价的齐次关系等式。 ( ，0 ，p ：) = ( e ，弓，1 ) 1o00 o10o oo10 - - - o 。q y q ：1 ( 2 2 ) 等式右边的矩阵称为平移变换矩阵，它由坐标系平移到点d 的坐标值来 决定，可简单表示为r ( o ) 。 丁( q ) = 100o o1o0 0010 9 ，9 yq ；1 1 2 ( 2 3 ) 2 e 0 只 = = = j y i i p p p + + + ： d d d 哈尔滨1 ：= 稃大学硕士学位论文 下面再分析一下向量在坐标系平移变换后的变换公式。如图2 3 所示， 向量v 在x 缈坐标系中的坐标表示为v = ( 毛y ，z ) 。为了考察向量v 在x y z 坐 标系中坐标表示( 匕，弓，吃) ，需要将v 的起始点平移到x y z 的原点q 。由于 坐标系x y z 和x y z 具有平行移动的关系，明显可以看出， “= ( 匕，匕) = ( 叱，匕) = v 。 y q x 图2 - 3 平移变换下的向量 如果将向量( 屹，_ ，v ：) 与四维向量( 1 ，0 ，匕，0 ) 对应起来，类似上面的 p = p t ( q 。) 式子仍然成立，即：( u ，b ，匕，o ) = ( 匕，b ，匕，o ) z ( q ) ，从而，三 维向量矛n _ - - 维的点都可以用四维向量统一表示出来。四维向量的第四个分量 又称为齐次坐标，四维向量的空间则称为齐次空间。