1、计算机辅助设计的发展与应用三维建模摘要：我们身在一个三维的世界中，三维的世界是立体的、真实的。同时，我们处于一个信息化的时代里，信息化的时代是以计算机和数字化为表征的。随着计算机在各行各业的广泛应用，人们开始不满足于计算机仅能显示二维的图像，更希望计算机能表达出具有强烈真实感的现实三维世界。三维建模可以使计算机作到这一点。所谓三维建模，就是利用三维数据将现实中的三维物体或场景在计算机中进行重建，最终实现在计算机上模拟出真实的三维物体或场景。而三维数据就是使用各种三维数据采集仪采集得到的数据，它记录了有限体表面在离散点上的各种物理参量。它包括的最基本的信息是物体的各离散点的三维坐标，
2、其它的可以包括物体表面的颜色、透明度、纹理特征等等。三维建模正在广泛地应用于越来越多的领域，并且以其提供直观、方便的三维图像等特点在各领域中发挥越来越重要的作用。关键字：三维建模、三维模型绘制、伞状网络1、三维数据的应用我们身在一个三维的世界中，三维的世界是立体的、真实的。同时，我们处于一个信息化的时代里，信息化的时代是以计算机和数字化为表征的。随着计算机在各行各业的广泛应用，人们开始不满足于计算机仅能显示二维的图像，更希望计算机能表达出具有强烈真实感的现实三维世界。三维建模可以使计算机作到这一点。所谓三维建模，就是利用三维数据将现实中的三维物体或场景在计算机中进行重建，最终实现在
3、计算机上模拟出真实的三维物体或场景。而三维数据就是使用各种三维数据采集仪采集得到的数据，它记录了有限体表面在离散点上的各种物理参量。它包括的最基本的信息是物体的各离散点的三维坐标，其它的可以包括物体表面的颜色、透明度、纹理特征等等。三维建模在建筑、医用图像、文物保护、三维动画游戏、电影特技制作等领域起着重要的作用。在建筑领域，一个建筑物如果用普通二维图片（比如照片）表示，会造成对某些细节部位或内部构造观察的不方便。而建造时使用的图纸虽然包含了大量的信息，对于非专业人士来说却不容易看懂而且很不直观。如果使用三维建模的方法重建出这个建筑的三维模型，那么就可以直接观察这个建筑的各个侧面
4、，整体构造，甚至内部的构造，这无论对于建筑师观看设计效果，还是对于客户观看都是很方便的。在医学方面，自从100年前伦琴发现X射线以来，医学图像处理技术已经经历了很长的路程。得到三维人体解剖图一直是人们努力追求的目标。德国汉堡大学医用数学和医用计算机研究所的Hohne教授领导的研究小组，开展了项目名称为Voxel-Man（体素和人）的解剖三维可视化研究。利用Voxel-Man的工具，医生可以模拟外科手术和立体定位或开洞。Voxel-Man具有极高的外科临床和教学价值，这在医学发展史上是一个新的里程碑。另一个三维建模在医学中的应用是虚拟手术。美国最负盛名的私立医院集团Maya
5、Clinic的生物医学图像处理资源中心，自70年代以来就致力于计算机生物医学图像的研究。在已有十余年经验的基础上，他们开发和设计了可以让外科医生观察CT和MRI数据的3D交互式外科辅助系统。医生可以在手术前预先规划手术方案，这样医生做手术就会更加准确，同时还可以在计算机上预演手术过程，使手术更安全。三维建模在文物保护中也发挥着重要的作用。有的文物或古建筑由于年代太久远或者各种侵蚀难以保存，有些文物有着珍贵的价值不能直接供人们观赏。可以利用三维建模将文物和古建筑通过影像采集、数字处理、数据压缩等技术制成三维形象，然后人们就可以随意的从各个角度观看和欣赏文物和古建筑，同时也是一
6、种保存和研究文物的办法。当数据积累到一定程度，还可以开展网络博物馆等文物展览项目，可以在保护文物的同时达到更广泛推广的目的。近年国内开始逐渐重视这方面的工作，比如故宫数字博物馆就在积极筹建中，其太和殿及其周边场景的三维模型就已经由日本凸版株式会社制作完成，实现了场景漫游，具有相当的真实感，细节表现也很优秀。在电脑游戏业高度发达的今天，尽量追求游戏的真实和画面的华丽几乎是所有制作者的共识。于是，三维游戏应运而生，开始仅仅是在游戏中加入三维动画，现在已经出现了全程使用三维场景的游戏，比如SquareSoft的FinalFantasy系列。以其优美的人物设计以及豪华的3D场景征服了
7、无数玩家，而成为风靡全球游戏FinalFantasyX的主人公球的畅销游戏。右上方的图像中是SquareSoft于2002年推出的大作FinalFantasyX中的男女主人公，从人物到场景，全都使用了三维模型，而且刻画极为精致细腻，有很好的视觉效果和冲击力。对比以前比较呆板的2D游戏，其在真实性和吸引力上的优势是显而易见的。在电影特技制作方面，三维建模技术也有着广泛的应用。起先，电影中的很多特殊场景如外星球、古代城市等都要通过搭建微缩模型来实现拍摄，不仅成本高、耗时长、后期制作困难，而且也不容易有真实的效果。对于某些危险的镜头，需要精密的布置和策划，采用各种防护措施，
8、最后还是不能保证万无一失。当三维建模技术被引进之后，现实世界中不可能出现的场景都可以被完美地构造出来，许多危险的镜头现在只需要在电脑前操作鼠标就可以完成，而且制作速度快、效果好。在最近的一两年，三维建模技术运用于电影制作取得了令人惊异的进展：出现了第一部完全由电脑制作的3D仿真电影一一最终幻想，这部由美国哥伦比亚三星电影公司出品的数字巨片耗资2.4亿美元，历时4年，它首次用电脑来制作所有的演员、道具、布景，影片中没有一个真人，但是虚拟演员在线条、毛发、皮肤、纹理、表情等方面已经几乎与真人别无二致。显示了电影中虚拟人物的3D模型和最后制成的效果，其真实程度之高让人不得不感叹三维建
10、并且将其组织成为一种表达与样本一致的结构的过程为三维数据的获取。采集样本三维信息的方法大致有以下几种：直接设计或测量：多用于早期建筑物三维模型的建立，用工程作图的方式得到模型的三视图。图像方法：只通过照片建立三维模型，用拍照的方式同时获得几何和纹理的信息，以此为基础重建样本的3D模型。机械探针(Mechanicalprobes)：通过机械探针和样本的物理接触采集表面数据。要求样本有一定硬度。体数据(Volumetricdata)恢复：使用样本的断层图象恢复出其三维形状。多用于医药部门，可使用的体数据包括X光图片、CT图片和MRT图片等。域扫描(Rangescanning)：通
11、过估算从测量仪器到样本表面点的距离来确定点在空间中的位置。包括光学三角测量，干涉测量等方法。在得到物体的三维数据后，建立三维模型的方法也是多种多样的。早期，三维模型大多是从三视图和照片用手工建立起来的，这类建模方法通常和某些软件结合在一起，常用的如3DStudio、AutoCAD、3DSMAX等。这样的方法在概念上有严格的数学描述，对几何形体有精确表达，可控制形状的平滑并有很多基于物理的高级建模工具。但这种方法需要物体的参数表达，模型不连续且在拓扑结构上不灵活。目前最流行的方式是用多边形网格来描述和绘制三维模型，它把三维模型表面的点连接成以多边形为单位的网格，是一种简单而高
12、效的表达方式。它可以表达复杂的表面，提供很强的适应性，其中尤以三角网格的使用最为广泛。相对于早期的手工建模，多边形网格的方法采用了分段线性拟合的思想，可以在物体表面不规则地采集样本点并完全不需要对物体进行参数化。因为上述的这些优点，多边形作为三维模型的基本要素已经被广泛地接受，多边形网格绘制的方法也获得了大部分计算机硬件的支持，而且出现了很多基于多边形网格的高级使用方法。由于不同获取方式得到的三维数据有不同的样式和特点，作为目前主流的建模方式，多边形网格绘制对不同的原始点数据有不同的建网策略。下面先给出原始点数据的一些不同格式。未组织数据(Unorganizeddata)：除了
13、采样点外没有其他附加信息。这是对物体最直接但在建模过程中计算复杂度最高的表达方式。轮廓数据(Contourdata)：在医药学应用中模型常被做成很薄的切片，并对每一个切片进行数字化得到一条轮廓线。这些轮廓线可被近似看做一组平行可交叠的闭合多边形。体数据(Volumetricdata):同样在医药学应用中，用MRT或CT得到的数据称为体数据。它们是一些三维栅格(3D-grid)，我们需要做的是从中提取模型的表面，可以使用著名的MarchingCubes方法。但这个方法得不到最优结果，如果体元栅格(Voxelgrid)边长取得过大，会在模型表面发生混淆而得到绘制效果不好的网格而
14、当其边长减小时，计算复杂度随其倒数做平方性增长。域数据(Rangedata)：通过域扫描得到的数据，并且已被规整化到同一坐标系下。这类数据通常是包含深度信息或三维点的矩形栅格，所以我们可以从中得到点的邻接信息。其获取难点是在不同扫描视点得到的各幅域图像上建立单一的网格。另一个问题是数据量的庞大，因为扫描时的采样是密集且均匀的。面对以上不同结构的数据，我们有不同的近似方式，所有这些方式可以分为两类。一类是插值(Interpolation)，这类方法中最后得到网格模型中的点就是初始的采样点；另一类是逼近(Approximation)，尤其对于采样点极其密集的域数据，一般采用逼近的方法
15、而不是插值。下面将介绍主要的近似方式。基于造型(Sculptingbased)的近似：属于插值类的方法，多用于未组织数据。这种近似方法一般先在点集合上建立四面体(通常使用Delaunay三角剖分的方法)，得到物体的整体形状，然后渐进地进行细化并取其合适的子集作为最终的网格。该方法适合从采样很稀疏的数据中重建表面，但计算复杂度和内存消耗都很大。基于体(Volumebased)的近似：属于逼近类的方法，可用于未组织数据，也可用于域数据等组织好的点云数据。对每个采样点估算一个方法中自定义的距离并把它们记入一个体元或八叉树的结构中，可以用MarchingCubes方法在这样的结构
16、中建立网格。算法复杂度由体元栅格的边长控制。增量法或区域增长法(Incremental/Region-growing)：该方法从一个选定的种子出发进行增长直到这个输入数据被覆盖。初始种子可以是一个三角面片、一条边、一幅域图像或者一个线框逼近(Wireframeapproximation)o不论在什么结构的数据上，全局建多边形网格的方法计算都比较复杂，表达繁琐，随着数据量的增大，其开销可能呈指数增长。这对于网络传输和实时绘制来说是不可接受的缺点。2.2三维激光扫描仪和点绘制在上一节提到域扫描技术，现在随着仪器技术的发展和软件支持的完善已经逐步普及，成为一种很重要的三维数据获取技
17、术，甚至引起了三维建模和绘制技术的革新。下面，先简略介绍域扫描的过程。第一步，定标。扫描过程中系统的坐标是由仪器的硬件和周围的环境共同决定的，所以事先要确定一个统一的坐标系。定标的工作对得到精确的三维数据是至关重要的。第二步，扫描。物体表面在一个视点被采样，得到一张密集的域图像。要进行多次的扫描才可以得到覆盖整个物体的采样图像。第三步，配准。扫描所得的采样图像都处在各自的局部坐标系中，它们必须被校准到同一个整体坐标系中。在具体获取数据的过程中，配准是要借助定标中确定的坐标系信息实现的。扫描小物体时可以固定扫描仪，记录物体放置台的转动角度，从而得到各个局部坐标系间的关系。而在扫描大场
18、景需要变换视点的时候，可以通过在场景中的固定位置摆放特殊标识物来标记各个局部坐标系，如Cyrax提供的有特殊反射率的靶标。接着，我们介绍两种常用的激光三维扫描仪FastScan和Cyrax。FastScan是被动式的手持激光三维扫描仪，多用于采集小型物体的三维数据。它由磁场定位系统和激光扫描系统组成。磁场定位系统包括磁场发射器和磁场接收器，激光扫描系统包括激光发射器和激光接收器。在扫描过程中，要求磁场发射器与被测物体尽量接近，最远不能超过75厘米。同时，激光扫描系统与被测物体距离应保持在15厘米到75厘米之间。当激光扫过物体表面时，两个CCD摄像头和激光扫描点之间构成三角形，根
20、得到激光在水平方向和垂直方向上的移动距离，通过这个距离计算出被测量点在水平和垂直方向上的坐标。重复上述过程就可以得到物体表面全部点的三维坐标。这个扫描仪的测距精度在50米以内可以达到26毫米而测量速度可以达到每秒一千点。采用域扫描技术得到的点云数据是密集的、均匀的。在显示的时候我们发现，把视点稍微拉远，就可以使得屏幕显示区域中每一个象素都至少有一个采样点，这时不需要建网也可以看到模型的三维效果。在如此密集的点云数据上直接建网会有很大的开销，而最后得到的网格对于显示来说也过于密集了。所以一般要先经过简化等步骤最后才能得到疏密合适的网格。但这是一个很漫长的计算过程，尤其是对表面几何形
21、状复杂的模型的建网过程，而且网格表达仍然需要局部的参数化表达，在多分辨率显示、压缩和传输等方面也很不方便。于是，在三维数据获取技术进步、密集点云数据普及而网格绘制不能适应其发展的情况下，点绘制引起了人们的重视。点绘制的思想在1983年就已经被提出，但直到2000年后才蓬勃发展起来。最初，点绘制被使用在表达某些透明物体上，如烟雾、火焰和水等。但现在点绘制已经被用来绘制不透明的固体模型，其中面临的主要难题就是如何表达出连续的表面。在网格绘制中，面片与面片之间是没有缝隙的，就不存在表面不连续的问题。但点绘制只显示物体表面的一些采样点，虽然这些点是很密集的，但仍然会在点与点之间出现空洞。
22、所以必须要有方法能填补模型表面的这些空洞，而这个方法又必须是快速的，否则就失去了点绘制的根本优势。要解决这个问题，最直接的想法就是扩大一个点的绘制区域。比如对于每一个点，绘制一个以它为中心、和它同法向量的小平面，这个小平面要保证覆盖住从这个点到周围不同方向上的几个点的区域的一半以上，则从这个点的法向量附近方向上看，其周围就不可能出现空洞。但用平面取代点还是达不到很好的效果，因为当几个相邻点法向量一致而不处于同一平面上时，用来代替点的小平面就会相互平行但不相交，从侧面看仍然有漏洞。于是，又有人用曲面取代点进行绘制，只要保证每个点的曲面和其周围曲面有相交，那从任何方向上看都不会有漏
23、洞。此外，还有用球体或椭球体来取代点进行绘制的方法，同样可以消除模型表面的空洞。在某些点绘制方法中，需要分析某个点的邻域性状，如该邻域内点分布密度、曲率变化等，通过这些性状来调整取代这个点的几何体的形状，得到更精确的模型表达和更好的绘制效果。从上面的描述中可以看到，点绘制是一种直接、简洁的绘制方式。由于它不需要对点云数据在全局上做任何处理，最多就是考虑点邻域内的信息，因此在速度上有着网格绘制无法比拟的优势，可以达到实时绘制的要求；而点绘制完全抛弃了连接信息，使得它的表达是精练的，它的存储量是极小的，给网络传输提供了方便。但同时也要看到，点绘制得到的三维模型只是在视觉效果上达到了表面
24、连续的要求，而无论从几何关系还是从拓扑关系上讲，它都不像网格绘制那样在模型的表面有连续性，这就造成了模型表达的不精确性。2.3基于局部分段线性拟合的绘制方法从前面的描述和分析中我们可以看到，全局建网的方法可以取得较好的视觉效果，但由于需要考虑整个点云数据的结构，算法的复杂度过高，不能适应实时传输和绘制的需要；点绘制是只考虑局部性状的方法，虽然快速，但不能精确和真实地表达模型。两种方法各有其优劣，且恰好补充了对方的不足。那么，是否存在一种折中的方法，使得其有网格的显示效果，又只需要考虑局部点云的信息呢？很自然的，我们想到了在局部建立网格的方法，就是下面要介绍的基于局部分段线性拟合的绘
25、制方法。三角网格的绘制方法有很好的视觉效果，说明以网格作为基本单位来近似地表达三维物体的表面是一个比较好的选择。而点绘制中，以一定大小的平面或某种曲面为基本单位就不能精确地表达三维物体的表面，但其基于局部信息来重建平面的思想是可取的。于是，我们就考虑找到一种局部的三角网格，以其为基本单位来表达三维物体的表面，但是这个局部三角网格应该有怎样的几何性状呢？考虑到要尽量达到良好的视觉效果，这样的网格应该和全局建立的网格有几何上的类似性。于是我们去观察已经建立网格的一个三维模型中的某一个点，发现它和它的几个近邻点之间都有网格的连接关系，以它自己为中心，形成了一个伞状网格。我们受到启发，就
26、使用这样的伞状网格作为我们正在寻找的局部三角网格。一般情况下，对点云数据中的某一个点，寻找离它距离最近的K个点，称为它的K近邻点，每两个相邻的近邻点和它本身连成一个三角面片，共K个三角面片组成了一个连续的伞状网格。于是，一个伞状网格就表示出了这个点及其周围一个邻域的几何性状。同样的，对点云数据中的每一个点都绘制以它为中心的K近邻伞状网格，可以肯定，在点云数据密度变化不大的情况下，这样密集的伞状网格能够覆盖整个三维模型，其中会有很多的重复，但是其局部网格的性状是规整和统一的。如此，三维模型就被这样的伞状网格表达出来了。需要指出的是，此处的K不是一个固定值，它可以随着点云的密度和该
27、点所在的位置而变化。具体说来，点云密集时，可以取K=8或10，而点云稀疏时，可以令K=6；当中心点位于模型的边缘时，只有一边有近邻点，就可以适当地减小K的值，此时的网格也不是伞状的。总之，要使最后得到的网格中面片尽量规整，比较接近全局建网方法所得到的网格，才有好的视觉效果。方法的具体描述请看本文第三章。下面我们来初步分析本方法与全局网格绘制及局部点绘制的异同，具体量化的比较请看本文的实验结果和分析部分。首先我们比较本方法和全局网格绘制的方法。从绘制效果上看，两个方法最后都是用网格来表达三维模型，所以应该有着相似的效果。不同之处在于，全局建网的方法得到的三角网格很规整、无重叠、无遗
28、漏，三角面片的数量少，模型表面更光滑。而本方法得到的网格会有交叉和重叠的情况，面片数量多；在某些特定区域，如点云密度有变化的区域，还会有空洞；模型表面也会出现一定数量的毛刺，尤其是在模型表面曲率发生不连续变化的边界区域，毛刺的情况比较明显。总体来说，本方法在视觉效果上要略逊全局网格绘制一筹。从算法复杂度来看，全局建网的方法需要考虑整个模型的拓扑结构，其计算过程是极其漫长的，而且一般需要人的手工干预，很难完全由电脑自动完成。随着数据量的增长，其复杂度可能出现指数级的增长，在三维模型越来越复杂的今天，这是几乎无法接受的缺点。本方法只考虑局部信息，这就比全局建网的方法在效率上有了显著的
30、状，相对于用一个平面或曲面来表达，这样的表达更精确。而且由于中心点和周围点有直接的连接关系，当以周围点为中心绘制同样的伞状网格时，只会出现重复和交叉，不会出现由于层次不同而产生的空洞。即是说，伞状网格表达比平面或曲面表达有更小的误差，而且伞状网格之间的拼接比之平面或曲面的拼接，更直接和容易，甚至只要判断是否重复而不需要其他特殊的考虑，省去了平面或曲面拟合的步骤，还能达到更好的拼接效果。因此，本方法得到的模型会比点绘制更平滑、更精致，在视觉效果上有比较明显的提升。从算法复杂度上看，两个方法都是基于局部点云数据的，在复杂度的变化趋势上有相似的表现，区别只是在处理每一个点的时候的计算
32、坐标。基于以上条件，本方法分成两个部分一一数据组织和绘制。数据组织就是对每一个需要计算的点寻找其K近邻，确定这些近邻点的连接顺序以便建立伞状网格，并且要使得伞状网格本身以及其中的三角面片尽量规整。然后用一种标准的格式来记录组织好的数据，为了网络传输的方便，要求这种标准格式的存储量尽量小。面临的主要问题如下：（1）需要计算的点的选择。在动手实验的过程中我发现由于伞状网格有极其高的重叠率，点云数据中有相当一部分的点，它们的伞状网格和已有网格是完全重合的，因此这一部分点可以不参与K近邻的搜索，从而减少计算量和存储量。通过分析，在本方法建立的模型中，一个点一般有K条边连接到它。当一个点
33、被作为中心点使用过后，其边数一般会达到或接近K。当一个没有当过中心点的点第一次被当作近邻点使用时，它的边数由零增加到三条（图3.1中点O作为点A的近邻点第一次被使用），此后每被当作近邻点使用一次，边数最少增加一条（图3.2中点O作为点B的近邻点被使用），最多增加三条（图3.3中点O作为点C的近邻点被使用）。所以，在这里我们规定一个点作为中心点最多被使用一次，而当它被作为近邻点使用（K-2）次后，就不再作为中心点使用了。（2）K近邻点的搜索。要求尽量快速地找到K近邻点，但并不需要近邻点是绝对精确的。（3）近邻点的组织。确定近邻点的连接顺序，使得它们最后连成的伞状网格退是一个对角线
34、和边不相交的多边形。在实现上，可以把近邻点映射到同一个平面上然后按照夹角来排序。（4）网格规整化。首先，要保证三角面片尽量规整，即三角形中没有过大栀也没有过小的角，如可以限定三角形的内角在30度到135度之间。其次，要保证伞状网格的规整性，要求近邻点比较均匀地分布在中心点周围，最好能包围住中心点。数据的记录。数据组织的结果是得到一个标准格式的文件，文件第一部分是所有点的三维坐标列表，每个点用三个浮点数表示，点在列表中的位置对应于该点的编号，第一行的点为第0号点，以此类推。文件第二部分是经过排序和规整化后的伞状网格列表，记录的是按一定规则排列的近邻点编号，其中第i行就代表以坐标列表中编
35、号为(i-1)号的点为中心点的近邻点。如列表中第三行是如下一个整数序列：6,15,0，84，则表示了由四个三角面片组成的一个伞状网格，这四个三角面片分别由编号为2，6，15、2，15，0、2,0，84、2,84,6的点组成。注意，在这种记录方式中，不会出现内角过小的三角面片，因为造成这种情况的近邻点可以从记录序列中删除而不会对其他面片造成影响。但这种记录方式无法消除内角过大的面片，于是我们引入了一个特殊的标识整数一2来阻止这种不规则面片的绘制。比如，前面提到编号为2的点周围有四个三角面片，但其中2,0，84这个面片内角大于135度了，不需要绘制，则我们可以把第三行的整
36、数序列改写为6,15,0，-2,84，在绘制时见到一2,就不去绘制2,0,84这个不规整面片了。还有一种特殊情况：点云数据中的有些点并1)，如第96号点不需要绘制以它为中心的网号点不需要绘制以它为中心的网格，则网格列表中的第97行用一个整数一1来标识，绘制时可以直接跳过。数据组织结束后，得到一个包含点坐标列表和伞状网格列表的文件，经过网络传输后就可以进入绘制的步骤。绘制就是根据既定的规则，把伞状网格列表转化成三角面片并将其实际显示5的描述。在这个过程中，要求快速并且达述。在这个过程中，要求快速并且达耀到较好的显示效果。重复面片的判断。前面说过，本方法在绘制中会出现很多的
38、在记录了所有需要绘制的面片后可以通过一定算法消除，但解决起来很繁琐。而这就违反了快速绘制的原则，因此，本文并没有解决这个问题，只是在3.3.2中提出了关于利用现有数据结构消除拓扑错误的初步想法。所谓模式识别，就是用计算机的方法来实现人对各种事物或现象的分析、描述、判断和识别。可以分为统计模式识别和结构模式识别，统计模式识别系统大致由以下四个部分组成：数据获取、预处理、特征提取和选择、分类决策。而K近邻方法多用于统计模式识别的分类决策中。所谓分类决策，就是把原始数据最能反映分类本质的特征提取出来之后，在特征空间中用统计方法把被识别对象归为某一类别。基本做法是在样本训练集基础上确
39、定某个判决规则，使按这种判决规则对被识别对象进行分类所造成的错误识别率最小或引起的损失最小。有时候，一个数据的分类特征并不显著，这时就可以找它在某一意义（比如欧氏距离）上的近邻数据，通过判断其近邻数据的分类特征，来决定该数据的分类。下面从模式识别的角度简略介绍一下近邻分类法中的K近邻法。接下来，我们分析用来进行网络传输的文件大小，并和建好网格的标准obj文件进行一个比较。注意，这里不考虑文件压缩，而仅仅比较原始状态下两个文件的大小。一个标准的obj文件分三个部分：第一部分是点的坐标，有3n个浮点数；第二部分是点的法向量，也有3n个浮点数；第三部分是三角网格，每一个网格用6个整数表
40、示，大约有2n个网格，共12n个整数。所以，在obj文件中，每个点对应12个整数和6个浮点数。由于本方法不需要使用点的法向量，我们生成的文件只有两部分：第一部分同样是点坐标，共3n个浮点数；第二部分是点的近邻点序列，这部分的大小随着近邻数K和搜索范围M而变化，同样使用上一节的四个模型，实验中得到的数据如表4.2所示。可以看到，当寻找6近邻时，近邻点个数在5n左右；寻找8近邻时，近邻点个数在6n左右。而当M变化时，会影响近邻搜索的精确性，从而对近邻点个数产生不大的影响。于是本方法中，每个点对应56个整数和3个浮点数，在存储空间上少于标准的obj文件。我们再来看绘制部分的空间代价。一
41、个n3维的double型矩阵来记录点的坐标。一个n维数组，其中的元素是k维型数组，用来记录所有点的近邻点数组，其总的存储量是5n6n个整数。接下来需要详细分析的是我们自己定义的数据结构RB树。表4.3给出了前面四个模型在寻找8近邻的情况下RB树的数目和所有树的叶结点个数之和。在前面介绍RB树的结构时已经指出，模型中的一个三角网格对应着一个叶结点，所以通过查看模型的网格数就可以很方便地知道叶结点的总数了。分析实验数据我们发现，RB树的数目接近n，即是有n个根结点，而叶结点数目大约为4n。再观察所有RB树的结构，发现其树干结点数大多为4,有一部分是3,其他情况较少，则大约有3n4
45、使用和点分布均匀时同样的阈值，在点较稀疏的区域就会找不到需要的点；但把阈值增大后，在点比较密集的区域就可能找到错误的点而产生错误的连接关系或在模型表面出现毛刺。综上所述，本方法对点云稀疏且分布不均匀的数据同样适用，但最终得到的效果会差一些。提高效果的关键在于边缘点和突变边界点判断过程中阈值的适当。从目前的分析来看，使用一个固定的阈值似乎很难达到要求的效果，以后可以考虑根据数据各个局部的不同特性，来取不同的阈值，应该可以达到更好的效果。4、讨论首先，本章将讨论目前本方法中还存在的问题和初步的改进方法。在前文中曾经提到以下7个问题：（1）更快速、更精确地搜索K近邻。如3.2.2中描述，现
47、系没有在本方法中被使用。实际上，这个想法是有一定价值的。如果对我们得到的模型进行消除拓扑错误并填补漏洞，最后得到的三角网格效果会和全局建网得到的网格非常接近。而消除拓扑错误的方法相对于局部建网的方法来说，其复杂度是很高的，但相对于全局建网的方法来说，它还是一个很快速、很简单的过程。因此，如果我们的这个想法是切实有效的，那么就等于开创了一条从局部建立理想全局网格的新道路，而且这个新方法在开销上要远远低于现有的全局建网方法。（4）边缘点和突变边界点的判断。这两种点在模型中是很特殊的点，需要用攀特殊的策略进行处理和绘制，否则会对最后的视觉效果产生不良影响。本方法采用的判断算法如3.2.4
48、描述。但是在4.2的最后一个实验中我们发现，这个判断算法在点云稀疏且分布不均匀的时候没有很好的效果，而且从其后的分析看来，这种不适应性是由算法本身的局限造成的。因此，这个算法有改进的必要。目前的想法是，当发现一个点的初试伞状网格无法规整化而需要进行边缘点和突变边界点的判断时，先求出该点所在局部点云密度大小及周围密度变化的情况，在密度大的区域或密度变大的方向上，把搜索判断的阈值设得小一些，反之则增大阈值。总之，使得判断算法对点云的局部密度变化有自适应性，而非通过单一阈值来控制。中我们提出了一种分析点云局部信息并改动算法使其与之相适应相适应的思路。可以把这种思路用在建立网格的过程中
49、，从而提升算法性能。（5）自适应建网。在实验中我们发现，模型的某个区域是一个平面或者接近一个平面，而对于密度大且分布均匀的点云数据来说，上面仍然有很密集的点。在全局建网中，可以先对这些点进行简化，只用几个大的三角网格来表示这个区域；而在本方法中，对于这样的点我们同样寻找其K近邻并绘制伞状网格。这是完全是没有必要的，甚至会产生毛刺对绘制结果有不良影响。因此，我们可以判断模型各区域的曲率变化情况，对于曲率变化大的区域，采用直接找K近邻的算法。对于曲率变化比较小的区域，则可以找中心点的t(t1)阶近邻，如t=2时，就找中心点的第K+1个到第2K个近邻，实行上述算法，再把其前K个近邻在点列表中标识为不可用。模型表面该区域曲率变化越