三维模型 论文

计算机辅助设计的发展与应用 三维建模 摘要： 我们身在一个三维的世界中，三维的世界是立体的、真实的。同时，我们处于一个 信息化的时代里，信息化的时代是以计算机和数字化为表征的。随着计算机在各行各业的广 泛应用，人们开始不满足于计算机仅能显示二维的图像，更希望计算机能表达出具有强烈真 实感的现实三维世界。三维建模可以使计算机作到这一点。所谓三维建模，就是利用三维数 据将现实中的三维物体或场景在计算机中进行重建，最终实现在计算机上模拟出真实的三维 物体或场景。而三维数据就是使用各种三维数据采集仪采集得到的数据，它记录了有限体表 面在离散点上的各种物理参量。它包括的最基本的信息是物体的各离散点的三维坐标，其它 的可以包括物体表面的颜色、透明度、纹理特征等等。三维建模正在广泛地应用于越来越多 的领域，并且以其提供直观、方便的三维图像等特点在各领域中发挥越来越重要的作用。关键字：三维建模、三维模型绘制、伞状网络1、三维数据的应用我们身在一个三维的世界中，三维的世界是立体的、真实的。同时，我们处于一个信息 化的时代里，信息化的时代是以计算机和数字化为表征的。随着计算机在各行各业的广泛应 用，人们开始不满足于计算机仅能显示二维的图像，更希望计算机能表达出具有强烈真实感 的现实三维世界。三维建模可以使计算机作到这一点。所谓三维建模，就是利用三维数据将 现实中的三维物体或场景在计算机中进行重建，最终实现在计算机上模拟出真实的三维物体 或场景。而三维数据就是使用各种三维数据采集仪采集得到的数据，它记录了有限体表面在 离散点上的各种物理参量。它包括的最基本的信息是物体的各离散点的三维坐标，其它的可 以包括物体表面的颜色、透明度、纹理特征等等。三维建模在建筑、医用图像、文物保护、 三维动画游戏、电影特技制作等领域起着重要的作用。在建筑领域，一个建筑物如果用普通 二维图片（比如照片）表示，会造成对某些细节部位或内部构造观察的不方便。而建造时使 用的图纸虽然包含了大量的信息，对于非专业人士来说却不容易看懂而且很不直观。如果使 用三维建模的方法重建出这个建筑的三维模型，那么就可以直接观察这个建筑的各个侧面， 整体构造，甚至内部的构造，这无论对于建筑师观看设计效果，还是对于客户观看都是很方 便的。在医学方面，自从 100 年前伦琴发现 X 射线以来，医学图像处理技术已经经历 了很长的路程。得到三维人体解剖图 一直是人们努力追求的目标。德国汉堡大学医用数 学和医用计算机研究所的 Hohne 教授领导的研究小组，开展了项目名称为 VoxelMan （体素和人）的解剖三维可视化研究。利用 VoxelMan 的工具，医生可以模拟外科手术 和立体定位或开洞。VoxelMan具有极高的外科临床和教学价值，这在医学发展史上是 一个新的里程碑。另一个三维建模在医学中的应用是虚拟手术 。美国最负盛名的私立医 院集团Maya Clinic的生物医学图像处理资源中心，自70年代以来就致力于计算机生物医 学图像的研究。在已有十余年经验的基础上，他们开发和设计了可以让外科医生观察 CT 和 MRI 数据的 3D 交互式外科辅助系统。医生可以在手术前预先规划手术方案，这样医 生做手术就会更加准确，同时还可以在计算机上预演手术过程，使手术更安全。三维建模在 文物保护中也发挥着重要的作用。有的文物或古建筑由于年代太久远或者各种侵蚀难以保 存，有些文物有着珍贵的价值不能直接供人们观赏。可以利用三维建模将文物和古建筑通过 影像采集、数字处理、数据压缩等技术制成三维形象，然后人们就可以随意的从各个角度观 看和欣赏文物和古建筑，同时也是一种保存和研究文物的办法。当数据积累到一定程度，还 可以开展网络博物馆等文物展览项目，可以在保护文物的同时达到更广泛推广的目的。近年 国内开始逐渐重视这方面的工作，比如故宫数字博物馆就在积极筹建中，其太和殿及其周边 场景的三维模型就已经由日本凸版株式会社制作完成，实现了场景漫游，具有相当的真实感， 细节表现也很优秀。在电脑游戏业高度发达的今天，尽量追求游戏的真实和画面的华丽几乎是所有制作者的 共识。于是，三维游戏应运而生，开始仅仅是在游戏中加入三维动画，现在已经出现了全程 使用三维场景的游戏，比如 Square Soft 的 Final Fantasy 系列。以其优美的人物设计以 及豪华的3D场景征服了无数玩家，而成为风靡全球游戏Final Fantasy X的主人公球的 畅销游戏。右上方的图像中是Square Soft于2002年推出的大作 Final Fantasy X中 的男女主人公，从人物到场景，全都使用了三维模型，而且刻画极为精致细腻，有很好的视 觉效果和冲击力。对比以前比较呆板的 2D 游戏，其在真实性和吸引力上的优势是显而易 见的。在电影特技制作方面，三维建模技术也有着广泛的应用。起先，电影中的很多特殊场 景如外星球、古代城市等都要通过搭建微缩模型来实现拍摄，不仅成本高、耗时长、后期制 作困难，而且也不容易有真实的效果。对于某些危险的镜头，需要精密的布置和策划，采用 各种防护措施，最后还是不能保证万无一失。当三维建模技术被引进之后，现实世界中不可 能出现的场景都可以被完美地构造出来，许多危险的镜头现在只需要在电脑前操作鼠标就可 以完成，而且制作速度快、效果好。在最近的一两年，三维建模技术运用于电影制作取得了 令人惊异的进展：出现了第一部完全由电脑制作的 3D 仿真电影最终幻想，这部 由美国哥伦比亚三星电影公司出品的数字巨片耗资 2.4 亿美元，历时 4 年，它首次用电脑 来制作所有的演员、道具、布景，影片中没有一个真人，但是虚拟演员在线条、毛发、皮肤、 纹理、表情等方面已经几乎与真人别无二致。显示了电影中虚拟人物的 3D 模型和最后制 成的效果，其真实程度之高让人不得不感叹三维建模技术的神妙。总之，三维建模正在广泛地应用于越来越多的领域，并且以其提供直观、方便的三维图 像等特点在各领域中发挥越来越重要的作用。在三维建模中，最主要的问题就是使用三维数据进行绘制，如何使得绘制出的模型有立 体感和真实感，要保证模型的表面平滑、无毛刺、无漏洞，达到比较理想的视觉效果；同时 还要较好地组织数据，减少存储空间以便于数据的传输和加快显示速度。下一章将介绍已有 的三维数据绘制方法以及本文提出的新方法。2、三维数据绘制方法2.1 三维数据的获取和网格绘制要建立真实物体的三维模型，首先要获取样本的相关属性，如几何形状、表面纹理等等。 记录这些信息的数据就称为三维数据，我们定义采集样本的信息并且将其组织成为一种表达 与样本一致的结构的过程为三维数据的获取。采集样本三维信息的方法大致有以下几种：直 接设计或测量：多用于早期建筑物三维模型的建立，用工程作图的方式得到模型的三视图。图像方法：只通过照片建立三维模型，用拍照的方式同时获得几何和纹理的信息，以此 为基础重建样本的3D模型。机械探针(Mechanical probes)：通过机械探针和样本的物理 接触采集表面数据。要求样本有一定硬度。体数据(Volumetric data)恢复：使用样本的断层图 象恢复出其三维形状。多用于医药部门，可使用的体数据包括X光图片、CT图片和MRT 图片等。域扫描(Range scanning)：通过估算从测量仪器到样本表面点的距离来确定点在空间 中的位置。包括光学三角测量，干涉测量等方法。在得到物体的三维数据后，建立三维模型 的方法也是多种多样的。早期，三维模型大多是从三视图和照片用手工建立起来的，这类建 模方法通常和某些软件结合在一起，常用的如 3D Studio、 Auto CAD、 3DS MAX 等。 这样的方法在概念上有严格的数学描述，对几何形体有精确表达，可控制形状的平滑并有很 多基于物理的高级建模工具。但这种方法需要物体的参数表达，模型不连续且在拓扑结构上 不灵活。目前最流行的方式是用多边形网格 来描述和绘制三维模型，它把三维模型表面的点连 接成以多边形为单位的网格，是一种简单而高效的表达方式。它可以表达复杂的表面，提供 很强的适应性，其中尤以三角网格的使用最为广泛。相对于早期的手工建模，多边形网格的 方法采用了分段线性拟合的思想，可以在物体表面不规则地采集样本点并完全不需要对物体 进行参数化。因为上述的这些优点，多边形作为三维模型的基本要素已经被广泛地接受，多 边形网格绘制的方法也获得了大部分计算机硬件的支持，而且出现了很多基于多边形网格的 高级使用方法。由于不同获取方式得到的三维数据有不同的样式和特点，作为目前主流的建模方式，多 边形网格绘制对不同的原始点数据有不同的建网策略。下面先给出原始点数据的一些不同格 式。未组织数据(Unorganized data)：除了采样点外没有其他附加信息。这是对物体最直接 但在建模过程中计算复杂度最高的表达方式。轮廓数据(Contour data)：在医药学应用中模 型常被做成很薄的切片，并对每一个切片进行数字化得到一条轮廓线。这些轮廓线可被近似 看做一组平行可交叠的闭合多边形。体数据(Volumetric data)：同样在医药学应用中， 用MRT或CT得到的数据称为体数据。它们是一些三维栅格(3D-grid),我们需要做的是 从中提取模型的表面，可以使用著名的 Marching Cubes 方法 。但这个方法得不到最优 结果，如果体元栅格(Voxel grid)边长取得过大，会在模型表面发生混淆而得到绘制效果 不好的网格而当其边长减小时，计算复杂度随其倒数做平方性增长。域数据(Range data)： 通过域扫描得到的数据，并且已被规整化到同一坐标系下。这类数据通常是包含深度信息或 三维点的矩形栅格，所以我们可以从中得到点的邻接信息。其获取难点是在不同扫描视点得 到的各幅域图像上建立单一的网格。另一个问题是数据量的庞大，因为扫描时的采样是密集 且均匀的。面对以上不同结构的数据，我们有不同的近似方式，所有这些方式可以分为两类。 一类是插值(Interpolation),这类方法中最后得到网格模型中的点就是初始的采样点；另一 类是逼近(Approximation)，尤其对于采样点极其密集的域数据，一般采用逼近的方法而不 是插值。下面将介绍主要的近似方式。基于造型(Sculpting based)的近似：属于插值类 的方法，多用于未组织数据。这种近似方法一般先在点集合上建立四面体(通常使用 Delaunay 三角剖分的方法)，得到物体的整体形状，然后渐进地进行细化并取其合适的子集 作为最终的网格。该方法适合从采样很稀疏的数据中重建表面，但计算复杂度和内存消耗都 很大。基于体(Volume based)的近似：属于逼近类的方法，可用于未组织数据，也可用于 域数据等组织好的点云数据。对每个采样点估算一个方法中自定义的距离并把它们记入一个 体元或八叉树的结构中，可以用 Marching Cubes 方法在这样的结构中建立网格。算法复 杂度由体元栅格的边长控制。增量法或区域增长法(Incremental / Region-growing)：该方法 从一个选定的种子出发进行增长直到这个输入数据被覆盖。初始种子可以是一个三角面片、 一条边、一幅域图像或者一个线框逼近(Wireframe approximation)。不论在什么结构的数 据上，全局建多边形网格的方法计算都比较复杂，表达繁琐，随着数据量的增大，其开销可 能呈指数增长。这对于网络传输和实时绘制来说是不可接受的缺点。2.2 三维激光扫描仪和点绘制 在上一节提到域扫描技术，现在随着仪器技术的发展和软件支持的完善已经逐步普及，成为 一种很重要的三维数据获取技术，甚至引起了三维建模和绘制技术的革新。下面，先简略介 绍域扫描的过程。第一步，定标。扫描过程中系统的坐标是由仪器的硬件和周围的环境共同决定的，所以事先 要确定一个统一的坐标系。定标的工作对得到精确的三维数据是至关重要的。 第二步，扫描。物体表面在一个视点被采样，得到一张密集的域图像。要进行多次的扫描才 可以得到覆盖整个物体的采样图像。第三步，配准。扫描所得的采样图像都处在各自的局部坐标系中，它们必须被校准到同一个 整体坐标系中。在具体获取数据的过程中，配准是要借助定标中确定的坐标系信息实现的。扫描小物体 时可以固定扫描仪，记录物体放置台的转动角度，从而得到各个局部坐标系间的关系。而在 扫描大场景需要变换视点的时候，可以通过在场景中的固定位置摆放特殊标识物来标记各个 局部坐标系，如 Cyrax 提供的有特殊反射率的靶标。 接着，我们介绍两种常用的激光三维 扫描仪FastScan和Cyrax。FastScan是被动式的手持激光三维扫描仪，多用于采集小型物体的三维数据。它由磁场定位系统和激光扫描系统组成。磁场定位系统包括磁场发射器 和磁场接收器，激光扫描系统包括激光发射器和激光接收器。在扫描过程中，要求磁场发射 器与被测物体尽量接近，最远不能超过 75 厘米。同时，激光扫描系统与被测物体距离应保 持在 15 厘米到 75 厘米之间。当激光扫过物体表面时，两个 CCD 摄像头和激光扫描 点之间构成三角形，根据三角测距原理，计算得到被扫描点与扫描仪的距离。同时，磁场接 收器收到磁场发射器的电磁信号，确定激光扫描仪在整个空间中的位置和姿态。这样，就能 计算出被扫描点的空间几何坐标。因此，在扫描过程中只要保持物体和磁场发射器的相对位置不变，系统本身就可以对扫 描得到的几何数据进行自动配准。Cyrax是主动式的激光三维扫描仪，需要支架和靶标，用 于室外大型场景和建筑物三维数据的采集。它采用了雷达测距的原理：数字脉冲式激光器将 激光以其固有的发射速度发射到物体表面后接受其返回信号，这个过程的时间和激光的发射 速度相乘再除以二，就可以得到扫描仪到被测量点的距离。再利用精密的水平方向和垂直方 向的偏转镜就可以得到激光在水平方向和垂直方向上的移动距离，通过这个距离计算出被测 量点在水平和垂直方向上的坐标。重复上述过程就可以得到物体表面全部点的三维坐标。这 个扫描仪的测距精度在 50 米以内可以达到 26 毫米而测量速度可以达到每秒一千点。 采用域扫描技术得到的点云数据是密集的、均匀的。在显示的时候我们发现，把视点稍微拉 远，就可以使得屏幕显示区域中每一个象素都至少有一个采样点， 这时不需要建网也可以 看到模型的三维效果。在如此密集的点云数据上直接建网会有很大的开销，而最后得到的网 格对于显示来说也过于密集了。所以一般要先经过简化等步骤最后才能得到疏密合适的网 格。但这是一个很漫长的计算过程，尤其是对表面几何形状复杂的模型的建网过程，而且网 格表达仍然需要局部的参数化表达，在多分辨率显示、压缩和传输等方面也很不方便。于是， 在三维数据获取技术进步、密集点云数据普及而网格绘制不能适应其发展的情况下，点绘制 引起了人们的重视。点绘制的思想在 1983 年就已经被提出，但直到 2000 年后才蓬勃发展 起来。最初，点绘制被使用在表达某些透明物体上，如烟雾、火焰和水等。但现在点绘制已 经被用来绘制不透明的固体模型，其中面临的主要难题就是如何表达出连续的表面。在网格 绘制中，面片与面片之间是没有缝隙的，就不存在表面不连续的问题。但点绘制只显示物体 表面的一些采样点，虽然这些点是很密集的，但仍然会在点与点之间出现空洞。所以必须要 有方法能填补模型表面的这些空洞，而这个方法又必须是快速的，否则就失去了点绘制的根 本优势。要解决这个问题，最直接的想法就是扩大一个点的绘制区域。比如对于每一个点， 绘制一个以它为中心、和它同法向量的小平面，这个小平面要保证覆盖住从这个点到周围不 同方向上的几个点的区域的一半以上，则从这个点的法向量附近方向上看，其周围就不可能 出现空洞。但用平面取代点还是达不到很好的效果，因为当几个相邻点法向量一致而不处于 同一平面上时，用来代替点的小平面就会相互平行但不相交，从侧面看仍然有漏洞。于是， 又有人用曲面取代点进行绘制，只要保证每个点的曲面和其周围曲面有相交，那从任何方向 上看都不会有漏洞。 此外，还有用球体或椭球体来取代点进行绘制的方法，同样可以消除 模型表面的空洞。在某些点绘制方法中，需要分析某个点的邻域性状，如该邻域内点分布密 度、曲率变化等，通过这些性状来调整取代这个点的几何体的形状，得到更精确的模型表达 和更好的绘制效果。从上面的描述中可以看到，点绘制是一种直接、简洁的绘制方式。由于它不需要对点云 数据在全局上做任何处理，最多就是考虑点邻域内的信息，因此在速度上有着网格绘制无法 比拟的优势，可以达到实时绘制的要求；而点绘制完全抛弃了连接信息，使得它的表达是精 练的，它的存储量是极小的，给网络传输提供了方便。但同时也要看到，点绘制得到的三维 模型只是在视觉效果上达到了表面连续的要求，而无论从几何关系还是从拓扑关系上讲，它 都不像网格绘制那样在模型的表面有连续性，这就造成了模型表达的不精确性。2.3 基于局部分段线性拟合的绘制方法 从前面的描述和分析中我们可以看到，全局建网的方法可以取得较好的视觉效果，但由于需 要考虑整个点云数据的结构，算法的复杂度过高，不能适应实时传输和绘制的需要；点绘制 是只考虑局部性状的方法，虽然快速，但不能精确和真实地表达模型。两种方法各有其优劣， 且恰好补充了对方的不足。那么，是否存在一种折中的方法，使得其有网格的显示效果，又 只需要考虑局部点云的信息呢？很自然的，我们想到了在局部建立网格的方法，就是下面要 介绍的基于局部分段线性拟合的绘制方法。 三角网格的绘制方法有很好的视觉效果，说明 以网格作为基本单位来近似地表达三维物体的表面是一个比较好的选择。而点绘制中，以一 定大小的平面或某种曲面为基本单位就不能精确地表达三维物体的表面，但其基于局部信息 来重建平面的思想是可取的。于是，我们就考虑找到一种局部的三角网格，以其为基本单位 来表达三维物体的表面，但是这个局部三角网格应该有怎样的几何性状呢？考虑到要尽量达 到良好的视觉效果，这样的网格应该和全局建立的网格有几何上的类似性。于是我们去观察 已经建立网格的一个三维模型中的某一个点，发现它和它的几个近邻点之间都有网格的连接 关系，以它自己为中心，形成了一个伞状网格。我们受到启发，就使用这样的伞状网格作为 我们正在寻找的局部三角网格。一般情况下，对点云数据中的某一个点，寻找离它距离最近 的 K 个点，称为它的 K 近邻点，每两个相邻的近邻点和它本身连成一个三角面片，共 K 个三角面片组成了一个连续的伞状网格。于是，一个伞状网格就表示出了这个点及其周围一 个邻域的几何性状。同样的，对点云数据中的每一个点都绘制以它为中心的K近邻伞状网 格，可以肯定，在点云数据密度变化不大的情况下，这样密集的伞状网格能够覆盖整个三维 模型，其中会有很多的重复，但是其局部网格的性状是规整和统一的。如此，三维模型就被 这样的伞状网格表达出来了。需要指出的是，此处的K不是一个固定值，它可以随着点云 的密度和该点所在的位置而变化。具体说来，点云密集时，可以取 K=8 或 10，而点云稀 疏时，可以令K=6；当中心点位于模型的边缘时，只有一边有近邻点，就可以适当地减小 K 的值，此时的网格也不是伞状的。总之，要使最后得到的网格中面片尽量规整，比较接近全 局建网方法所得到的网格，才有好的视觉效果。方法的具体描述请看本文第三章。下面我们来初步分析本方法与全局网格绘制及局部点绘制的异同，具体量化的比较请看 本文的实验结果和分析部分。首先我们比较本方法和全局网格绘制的方法。从绘制效果上看，两个方法最后都是用网 格来表达三维模型，所以应该有着相似的效果。不同之处在于，全局建网的方法得到的三角 网格很规整、无重叠、无遗漏，三角面片的数量少，模型表面更光滑。而本方法得到的网格 会有交叉和重叠的情况，面片数量多；在某些特定区域，如点云密度有变化的区域，还会有 空洞；模型表面也会出现一定数量的毛刺，尤其是在模型表面曲率发生不连续变化的边界区 域，毛刺的情况比较明显。总体来说，本方法在视觉效果上要略逊全局网格绘制一筹。从算 法复杂度来看，全局建网的方法需要考虑整个模型的拓扑结构，其计算过程是极其漫长的， 而且一般需要人的手工干预，很难完全由电脑自动完成。随着数据量的增长，其复杂度可能 出现指数级的增长，在三维模型越来越复杂的今天，这是几乎无法接受的缺点。本方法只考 虑局部信息，这就比全局建网的方法在效率上有了显著的提升。而且对于每一个点来说，计 算复杂度基本是固定的，因此，整个算法的复杂度随着点的增加做线性增长，使得本方法适 用于大数据量的场合。最后，在绘制的过程中，全局建网的方法需要记录的信息繁多，除了 点坐标外还要记录面的组合方式，而且需要按照一定的顺序和规则进行存储，这就给网络传 输和快速绘制带来了不便。而本方法只需要记录点坐标及其近邻点编号，而且可以无序存储， 保证了网络传输的快捷并支持实时绘制。总而言之，在时间和空间代价上，本方法相对于全 局网格绘制的方法拥有相当明显的优势。接着我们比较本方法和局部点绘制的方法。从绘制 效果上看，在每一个局部，我们用一个伞状网格来表达点及其周围一个邻域的几何性状，相 对于用一个平面或曲面来表达，这样的表达更精确。而且由于中心点和周围点有直接的连接 关系，当以周围点为中心绘制同样的伞状网格时，只会出现重复和交叉，不会出现由于层次 不同而产生的空洞。即是说，伞状网格表达比平面或曲面表达有更小的误差，而且伞状网格 之间的拼接比之平面或曲面的拼接，更直接和容易，甚至只要判断是否重复而不需要其他特 殊的考虑，省去了平面或曲面拟合的步骤，还能达到更好的拼接效果。因此，本方法得到的 模型会比点绘制更平滑、更精致，在视觉效果上有比较明显的提升。从算法复杂度上看，两 个方法都是基于局部点云数据的，在复杂度的变化趋势上有相似的表现，区别只是在处理每 一个点的时候的计算复杂度。收集邻域信息是两个方法都要做的，对收集到信息的计算是本 方法更复杂，而在后期对整个模型的整合方面点绘制的方法要复杂一些，但都没有数量级上 的差异。可以说，计算的快速和简单是两个方法共同的优点。同样的，在绘制的过程中，两 个方法需要存储的信息量也没有大的差别，都能适应网络传输和实时绘制。综上所述，因为 算法思路的相似，在时间和空间代价上，本方法和局部点绘制的方法不相伯仲。3、基于局部分段线性拟合的点云数据绘制方法3.1 总体描述和主要问题本方法的提出主要是为了通过网络传输实现快速绘制，要求在保证绘制质量的前提下数 据量小、计算简单快捷，方法的原始数据是点云数据，只包含了各个三维点在空间中的坐标。 基于以上条件，本方法分成两个部分数据组织和绘制。 数据组织就是对每一个需要计 算的点寻找其 K 近邻，确定这些近邻点的连接顺序以便建立伞状网格，并且要使得伞状 网格本身以及其中的三角面片尽量规整。然后用一种标准的格式来记录组织好的数据，为了 网络传输的方便，要求这种标准格式的存储量尽量小。面临的主要问题如下：（1）需要计算的点的选择。在动手实验的过程中我发现由于伞状网格有极其?高的重叠率， 点云数据中有相当一部分的点，它们的伞状网格和已有网格是完全重合的，因此这一部分点 可以不参与 K 近邻的搜索，从而减少计算量和存储量。通过分析，在本方法建立的模型中， 一个点一般有 K 条边连接到它。当一个点被作为中心点使用过后，其边数一般会达到或 接近K。当一个没有当过中心点的点第一次被当作近邻点使用时，它的边数由零增加到三 条（图 3.1 中点 O 作为点 A 的近邻点第一次被使用），此后每被当作近邻点使用一次，边 数最少增加一条（图 3.2 中点 O 作为点 B 的近邻点被使用），最多增加三条（图 3.3 中 点 O 作为点 C 的近邻点被使用）。所以，在这里我们规定一个点作为中心点最多被使用一 次，而当它被作为近邻点使用（K2）次后，就不再作为中心点使用了。（2）K 近邻点的搜索。要求尽量快速地找到 K 近邻点，但并不需要近邻点?是绝对精确 的。（3）近邻点的组织。确定近邻点的连接顺序，使得它们最后连成的伞状网格退是一个对角 线和边不相交的多边形。在实现上，可以把近邻点映射到同一个平面上然后按照夹角来排序。（4）网格规整化。首先，要保证三角面片尽量规整，即三角形中没有过大栀也没有过小的 角，如可以限定三角形的内角在 30 度到 135 度之间。其次，要保证伞状网格的规整性， 要求近邻点比较均匀地分布在中心点周围，最好能包围住中心点。（5）数据的记录。数据组织的结果是得到一个标准格式的文件，文件第一部分是所有点的 三维坐标列表，每个点用三个浮点数表示，点在列表中的位置对应于该点的编号，第一行的 点为第 0 号点，以此类推。文件第二部分是经过排序和规整化后的伞状网格列表，记录的 是按一定规则排列的近邻点编号，其中第i行就代表以坐标列表中编号为（i1）号的点 为中心点的近邻点。如列表中第三行是如下一个整数序列：6， 15， 0， 84，则表示了由四 个三角面片组成的一个伞状网格，这四个三角面片分别由编号为2， 6， 15、2， 15， 0、 2， 0， 84、2， 84， 6的点组成。注意，在这种记录方式中，不会出现内角过小的三角面 片，因为造成这种情况的近邻点可以从记录序列中删除而不会对其他面片造成影响。但这种 记录方式无法消除内角过大的面片，于是我们引入了一个特殊的标识整数2 来阻止这种不 规则面片的绘制。比如，前面提到编号为 2 的点周围有四个三角面片，但其中2， 0， 84 这个面片内角大于 135 度了，不需要绘制，则我们可以把第三行的整数序列改写为6， 15， 0，2， 84，在绘制时见到2，就不去绘制2， 0， 84这个不规整面片了。还有一种特殊 情况：点云数据中的有些点并 1 ），如第 96 号点不需要绘制以它为中心的网 号点不需要 绘制以它为中心的网格，则网格列表中的第 97 行用一个整数1 来标识，绘制时可以直接 跳过。数据组织结束后，得到一个包含点坐标列表和伞状网格列表的文件，经过网络传输后 就可以进入绘制的步骤。绘制就是根据既定的规则，把伞状网格列表转化成三角面片并将其 实际显示 5 的描述。在这个过程中，要求快速并且达述。在这个过程中，要求快速并且达 耀到较好的显示效果。（6）重复面片的判断。前面说过，本方法在绘制中会出现很多的重复面片，一如果对每一 个面片都进行绘制的话会浪费大量的时间，甚至会对最后的绘制效果产生不良影响。因此， 我们必须定义一种结构来记录已经绘制的面片，这种结构首先要能够实现快速检索，其次要 便于插入新的数据，还要尽量节省存储空间。（7）面片的拓扑错误。本方法绘制的网格中，面片除了重复之外，还会出现交叉，如图 3.4 中比较粗的线段所示，面片 ABC 与面片 ABD 就发生了交叉的拓扑错误。一般情况下， 这种错误对视觉效果不会产生大的影响，但有时候，这种交叉现象会在模型表面造成小的空 洞，这种空洞只有在某个特定方向上可见。从算法上分析，这种拓扑错误在数据组织的过程 中是必然会出现的，在绘制的过程中也很难消除，只有在记录了所有需要绘制的面片后可以 通过一定算法消除，但解决起来很繁琐。而这就违反了快速绘制的原则，因此，本文并没有 解决这个问题，只是在 3.3.2 中提出了关于利用现有数据结构消除拓扑错误的初步想法。所 谓模式识别，就是用计算机的方法来实现人对各种事物或现象的分析、描述、判断和识别。 可以分为统计模式识别和结构模式识别，统计模式识别系统大致由以下四个部分组成：数据 获取、 预处理、特征提取和选择、分类决策。而 K 近邻方法多用于统计模式识别的分 类决策中。所谓分类决策，就是把原始数据最能反映分类本质的特征提取出来之后，在特征 空间中用统计方法把被识别对象归为某一类别。基本做法是在样本训练集基础上确定某个判 决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最 小。有时候，一个数据的分类特征并不显著，这时就可以找它在某一意义（比如欧氏距离） 上的近邻数据，通过判断其近邻数据的分类特征，来决定该数据的分类。下面从模式识别的 角度简略介绍一下近邻分类法中的 K 近邻法。接下来，我们分析用来进行网络传输的文件大小，并和建好网格的标准 obj 文件进行 一个比较。注意，这里不考虑文件压缩，而仅仅比较原始状态下两个文件的大小。一个标准 的 obj 文件分三个部分：第一部分是点的坐标，有 3n 个浮点数；第二部分是点的法向量， 也有 3n 个浮点数；第三部分是三角网格，每一 个网格用 6 个整数表示，大约有 2n 个网 格，共 12n 个整数。所以，在 obj 文件中，每个点对应 12 个整数和 6 个浮点数。由于 本方法不需要使用点的法向量，我们生成的文件只有两部分：第一部分同样是点坐标，共 3n 个浮点数；第二部分是点的近邻点序列，这部分的大小随着近邻数 K 和搜索范围 M 而变 化，同样使用上一节的四个模型，实验中得到的数据如表 4.2 所示。可以看到，当寻找 6 近邻时，近邻点个数在 5n 左右；寻找 8 近邻时，近邻点个数在 6n 左右。而当 M 变化 时，会影响近邻搜索的精确性，从而对近邻点个数产生不大的影响。于是本方法中，每个点 对应56个整数和3个浮点数，在存储空间上少于标准的obj文件。 我们再来看绘制部分的空间代价。一个 n?3 维的 double 型矩阵来记录点的坐标。一个 n 维数组，其中的元素是 k 维型数组，用来记录所有点的近邻点数组，其总 的存储量是 5n6n 个整数。接下来需要详细分析的是我们自己定义的数据结构 RB 树。表 4.3 给出 了前面四个模型在寻找 8 近邻的情况下 RB 树的数目和所有树的叶结点个数之和。在前面 介绍 RB 树的结构时已经指出，模型中的一个三角网格对应着一个叶结点，所以通过查看 模型的网格数就可以很方便地知道叶结点的总数了。分析实验数据我们发现， RB 树的数目 接近n即是有n个根结点，而叶结点数目大约为4n。再观察所有RB树的结构，发现 其树干结点数大多为 4，有一部分是 3，其他情况较少，则大约有 3n 4n 个树干结点。 每一个结点包含一个整数，根结点和叶结点各有一个指针，而树干结点有两个指针。所以， RB树总的空间开销是7n8n个整数和lln12n个指针。相对于标准obj文件用12n 个整数记录连接关系，这个开销要大一些， 但可以实现快速检索。3.2 接着是其时间代价。此处为了集中精力在算法的讨论上，我们忽略了实际绘制的时间，只计算输入数据和判 断三角面片是否要绘制的时间。输入部分要读入3n个浮点数和5n6n个整数，时间复杂 度是 O(n) 。而判断的过程其实就是一个建立和搜索 RB 树的过程。按照前面的结论， 约有6n个面要参加判断，但最后只绘制了 4n个。所以，共进行了 4n次插入和6n次搜 索，平均每次插入要进行 2 次整数赋值和 2 次指针赋值，平均每次搜索要进行 4 次取值 和比较。其时间复杂度也是 O(n) 。所以，整个过程应该是随着点数的增大做线性增长的。 可以看见，矿石模型、马的模型和人嘴模型的点数比大约是2.49：2.05：1，当 M=320 时， 其输入过程消耗时间比大约是 2.21：1.90：1，计算过程消耗时间比大约是 2.72：2.12：1； 当M=640时，其输入过程消耗时间比大约是2.14： 1.80： 1,计算过程消耗时间比大约是 2.60： 1.79： 1。输入时间和计算时间随着 n 的增大都呈现明显的线性增长趋势，而当 M 变 化时，对时间开销没有大的影响。从消耗时间的绝对量上看，计算的过程最多是 0.2 秒， 完全满足快速判断的要求，说明我们的 RB 树结构设置是成功的。通过比较发现，我们的算法在时间代价上要大大优于这些方法，这得益于我们基于局部 考虑问题的思路。当然，我们在网格的性状和最后的视觉效果上也付出了一定的代价。这样 的空洞就少了很多，底部也没有了连接错误。说明在点云稀疏且不均匀的时候，适当增大 M 同样会改进算法的效果。随着 K 的增大，在模型上已经基本看不见空洞，只有少量毛刺， 这也是由边缘点和突变边界点判断中取了过大的阈值引起的。说明适当增大 K 同样可以 改进算法效果。但是，在这个实验中，总是出现判断阈值过大的问题。分析其原因如下：当 点分布不均匀的时候，如果使用和点分布均匀时同样的阈值，在点较稀疏的区域就会找不到 需要的点；但把阈值增大后，在点比较密集的区域就可能找到错误的点而产生错误的连接关 系或在模型表面出现毛刺。综上所述，本方法对点云稀疏且分布不均匀的数据同样适用，但最终得到的效果会差一 些。提高效果的关键在于边缘点和突变边界点判断过程中阈值的适当。从目前的分析来看， 使用一个固定的阈值似乎很难达到要求的效果，以后可以考虑根据数据各个局部的不同特 性，来取不同的阈值，应该可以达到更好的效果。4、讨论首先，本章将讨论目前本方法中还存在的问题和初步的改进方法。在前文中曾经提到以下7 个问题：(1) 更快速、更精确地搜索 K 近邻。如 3.2.2 中描述，现有 K 近邻算法的复杂度仍然 很高，而本方法中采用预先设定搜索范围的方法又会对精确度造成影响。所以，如果能找到 一种更快速、更精确的 K 近邻搜索方法，将会大幅度提升本方法的表现。(2) 减少存储量。在 4.1 中我们详细分析了本方法的空间开销及记录文件的昀存储量。 发现其用来传输的中间文件其记录方式略优于标准 obj 文件，但绘制过 程中要记录的信息 量比较大。如何减少或压缩这些信息是将来需要做的一个重要工作。(3) 拓扑错误的消除。拓扑错误的定义参看3.1中的问题07从算法上分析，在本方法 中拓扑错误是无法避免的，但它对最后的视觉效果没有大的影响。我们想到了一种消除拓扑 错误的方法，但由于其空间时间代价过高的关系没有在本方法中被使用。实际上，这个想法 是有一定价值的。如果对我们得到的模型进行消除拓扑错误并填补漏洞，最后得到的三角网 格效果会和全局建网得到的网格非常接近。而消除拓扑错误的方法相对于局部建网的方法来 说，其复杂度是很高的，但相对于全局建网的方法来说，它还是一个很快速、很简单的过程。 因此，如果我们的这个想法是切实有效的，那么就等于开创了一条从局部建立理想全局网格 的新道路，而且这个新方法在开销上要远远低于现有的全局建网方法。(4) 边缘点和突变边界点的判断。这两种点在模型中是很特殊的点，需要用攀特殊的策略 进行处理和绘制，否则会对最后的视觉效果产生不良影响。本方法采用的判断算法如 3.2.4 描述。但是在 4.2 的最后一个实验中我们发现，这个判断算法在点云稀疏且分布不均匀的 时候没有很好的效果，而且从其后的分析看来，这种不适应性是由算法本身的局限造成的。 因此，这个算法有改进的必要。目前的想法是，当发现一个点的初试伞状网格无法规整化而 需要进行边缘点和突变边界点的判断时，先求出该点所在局部点云密度大小及周围密度变化 的情况，在密度大的区域或密度变大的方向上，把搜索判断的阈值设得小一些，反之则增大 阈值。总之，使得判断算法对点云的局部密度变化有自适应性，而非通过单一阈值来控制。 中我们提出了一种分析点云局部信息并改动算法使其与之相适应相适应的思路。可以把这种 思路用在建立网格的过程中，从而提升算法性能。(5) 自适应建网。在实验中我们发现，模型的某个区域是一个平面或者接近?一个平面，而 对于密度大且分布均匀的点云数据来说，上面仍然有很密集的点。在全局建网中，可以先对 这些点进行简化，只用几个大的三角网格来表示这个区域；而在本方法中，对于这样的点我 们同样寻找其 K 近邻并绘制伞状网格。这是完全是没有必要的，甚至会产生毛刺对绘制 结果有不良影响。因此，我们可以判断模型各区域的曲率变化情况，对于曲率变化大的区域， 采用直接找 K 近邻的算法。对于曲率变化比较小的区域，则可以找中心点的 t (t 1) 阶近邻，如t =2时，就找中心点的第K+1个到第2K个近邻，实行上述算法，再把其前K个近邻在点列表中标识为不可用。模型表面该区域曲率变化越小，则t的取值越大； 当该区域很接近一个平面时，甚至可以直接取其边界点作为中心点的近邻点。这就相当于对 点云进行了简化，消除了曲率变化小的区域中多余的点。但这又引发了简化和搜索的先后顺 序、简化后点云的重新组织、用伞状网格逼近平面的精确性度量、平面上合适中心点的选择 等等问题，需要对算法做根本上的调整。总之，自适应建网是一个很复杂的问题，在这里我 们只是单纯地把原始想法记录下来，并不做深入探讨也不保证其可行性。接下来，我们讨论 全局建网和点绘制中的一些技术应用于本方法的可能性。 /(6) 平滑(Smoothing)。在点云数据的获取过程中会有噪声的干扰，也会因为失真而出现 度量错误。为了消除这些错误，需要对模型做平滑。对于全局网格来说，一个比较经典的平 滑算子是离散拉普拉斯平滑算子。它寻找位于某个点单环形邻域(One-Ring Formed) 内的点，并把这个点移动到寻找到的这些点的质心。很明显，这种方法对任何网格模型都适 用，可以直接移植到我们的方法上而改进模型的显示效果。而如果我们把单环形邻域改成点 的近邻区域，还可以把这个平滑算子直接应用在点云数据上，这就是在点绘制中的平滑算法。(7) 多分辨率。一个多分辨率的实现过程一般分为简化、获取细节信息和精细化几个部分， 有的多分辨率系统还提供了选择性细化的方法。所谓简化就是在一定的误差控制范围内，用 比较粗略的网格去近似原网格模型。通常，要求初始网格是规整的，而简化要通过使得规整 化能量最小来控制。显然，这种简化的方法不适合我们的模型，因为我们的网格有重叠和拓 扑错误。而在点绘制的算法中，有直接对点云数据进行的简化，可以运用在我们的方法中得 到全局建网中简化同样的效果。大概的思路 就是在不影响模型形状的前提下消除点云中 的冗余点，对于每一个点都定义形状、法向、颜色等的信息度量，通过计算逐步删去信息熵 最小的点。然后就是细节信息的获取，因为要从简化的模型中恢复出精细的模型，所以简化 前模型的细节信息是必须要被获取和记录的，这在全局建网、点绘制和本方法中都是一样的。 最后是精细化的过程，和简化过程一样，全局建网中的细化方法是不适用于我们的模型的， 而在点绘制中使用的细化方法则可以直接运用在我们的方法里。从上面看来，本方法支持多 分辨率绘制，但具体的实现过程应该更接近点绘制。综上所述，本方法还有很多地方可以改进，对现存很多三维处理技术都有兼容性。而且 在某些方面，可以把网格处理和点处理的技术结合起来。可以说，这个方法提供了另一种建 立和使用网格模型的方式，更直接、更快速。致谢首先我衷心地感谢我的老师孙永华，在这的一学期的学习中，从确定论文题目的选题， 到完成论文都离不开她的指导。对于遇到的各种问题，总会想起孙老师的耐心讲解，同时给 我们教授了思路。孙老师精益求精的学术精神和严谨的治学态度时刻感染着我。感谢同学们 和朋友们在学习和生活上的帮助和支持。我还要感谢我的家人。他们远在千里之外，却时刻 关注我的情况，令我能全心投入学习中去。他们给了我最深切的关怀和莫大的支持，他们是 我坚持不懈地投入学业的精神支柱。参考文献1. 数学手册编写组：数学手册。 北京，人民教育出版社，88-89 页，1979。2. S.巴斯 著，朱洪 等译：计算机算法：设计和分析引论。上海，复旦大学出版1985。3. 边肇祺：模式识别。北京，清华大学出版社， 1987。4 Lars Linsen: Point Cloud Representation. Technical report No. 2001-3, Fakultaetfuer Informatik, Universitaet Karlsruhe, 2001.5. Linsen, Prautzsch,: Local Versus Global Triangulations. Eurographics 2001 Proceedings, Short Presentations, 2001.