密集点模式的三维场景重构技术概述

黄志辉1 叶达忠2
（1.广西地质矿产局272地质队 广西南宁 530031；
2.广西水利电力勘测设计研究院 广西南宁 530023）

【摘　要】　本文对点模式图形学进行研究，论述点模式图形学的应用前景，描述三维场景重构所需的关键技术，包括三维点云的数据组织、简化、修补、表面着色等等概念进行论述。
【关键字】　点云 点元 三维场景重构 点阵图形

　　1 前言
　　近年来，计算机三维图形学研究与发展方向发生了显著的变化，随着计算机硬件技术的迅速发展，计算速度飞跃变化，矢量图形正向点阵图形方向演变。
　　作为一种新的计算机图形技术，点模式的图形处理技术有着大量的难题有待研究，其中点模式的三维场景的重构是其中的关键技术。为说明问题，本文从点模式图形学概念、三维场景重构关键技术、场景显示三个方面进行论述。
　　2 点模式图形学
　　点阵图形中三维点基元表示空间实体表面是一种新的计算机图形表示方法，目前正经历了一个伟大的复兴，图形处理工作者很多的研究工作已经集中致力于采样点元的有效表示、建模、处理与绘制点采样几何造型。事实上，点是最简单、最基本的几何定义实体。点作为显示基元早就提出来，然而，只是近来才被越来越多的学者所关注。学者们能够对点基元产生新的兴趣源于两个因素。一方面，计算机图形模型的多边形复杂度在急剧增长，为管理、处理、操作这类大规模多边形网格的连通信息带来很多困难，这使得一些处在图形学研究前沿的学者开始思考作为基本图元的多边形的未来前途。另一方面，现代3D数字摄影与3D扫描系统可以迅速采集客观世界中任何复杂物体的几何与外观信息，这些技术产生了海量的点采样。这些点是表示3D物体的几何与外观信息的离散构件，这恰如像素是图像的基本数字元素。
　　基于点的计算机图形学是一个新的图形学，近来才被越来越多的学者所关注，而基于点的数字城市三维建模技术目前国外开始有人进行研究，并取得了一些研究成果。
　　三角网格在许多计算机图形应用邻域中仍旧是最通用的曲面表示方式。由于它的简单和灵活，在一些注重处理性能的领域，三角网格取代了传统的CAD曲面表示，如NURBS曲面。
　　虽然三角网格比NURBS灵活，但它也在某些应用中存在着限制和不足。很多建立在三角网格上的算法要求拓扑一致的二维流形曲面，因此，在网格生成中，需要进行流形抽取和拓扑净化。在网格处理的整个流程中维护拓扑一致使得这些算法有时会非常复杂，即使在最终的目标应用程序（如可视化）根本无需一致拓扑性的情况下也同样面临这个问题。而动态网格连通恰是一个拓扑关系频繁发生改变的例子，有时为了避免极度变形后的巨大拉伸需要局部重构，而有时为了对感兴趣的特定区域提供更多的变形自由度，也需要局部重构。在这种情况下，对于那些无需全局一致的曲面拓扑关系的应用程序（如可视化）而言，基于点的表示允许更灵活的操作。因此，进一步发展的更简单、灵活的基元应该是利用无结构点云或小圆盘，无需存储维护全局一致的连通信息。
　　从绘制的角度，当网格变得越来越复杂而屏幕分辨率增长相对较慢，此时三角网格则不太适合了。CPU和图形硬件性能的稳定增长，廉价的内存，以及三维扫描仪的广泛使用，导致了产生或生成了大量的高精度的几何数据，包含几百万三角片的模型在当今已经很多。当三角片的数量多于屏幕像素数时，绘制这样大量的数据往往导致一个三角形的投影区域不足一个像素。在这种情况下，传统的增量式光栅方法则很低效，因为绘制三角形的代价高昂。因此，点更胜任这种高度复杂模型的绘制基元这一角色。
　　作为一种曲面表示方法，基于点的曲面造型之所以受到了广泛关注，是因为在处理高度复杂的3D模型时，它可以实现高效地绘制和灵活的几何处理。点采样对象无需存储与维护全局一致的拓扑信息，因此，与三角网格相比，在处理高度复杂、动态改变的模型时具有更大的灵活性。
　　从国外的研究成果上看，虽然目前尚未达到完成研究计划，但商业化前景已经非常明显，2006年微软专门针对数字长城制定了一个计划，准备将目前的研究技术运用在中国的数字奥运、数字长城等等项目上。中国科学院自动化研究所最近在基于点的重建上进行了一些研究，并将成果运用到虚拟人数据集可视化，采用点模式的大脑图形与古建筑模型成果如下：

　　国内采用点模式的图形学方法实现数字城市三维建模研究目前尚无人进行研究，与国外接近使用的技术水平相比，加紧研究的紧迫性非常迫切。
　　3 场景重构关键技术
　　通常，由三维数字相机、三维扫描系统等数据获取设备或采取基于图象的重建方法获取三维模型表面大量的采样点数据，这些采样点数据量是海量的，为了更方便、更容易地对采样点进行处理，需将采样点数据组织成某种层次结构，如K-D树、八叉树、BSP树等[1]；由于物理测量上的误差以及模型表面材料反射特性的原因，往往带有一定的噪音和失真，因此，在将这些数据进一步使用前，需要对其进行必要的预处理，如：对采样点数据进行去噪、对重复扫描的模型表面采样点数据进行配准以及对不完整的数据模型进行修复（即：模型补洞）等等；基于采样点数据对模型表面进行三角化，构成了采样点模型的三角网格表示的模型；对采样点数据进行曲面重建，就会转换成由NURBS曲面或RBF、MPU等隐式曲面表示的模型，对模型表面采样点数据的处理构成了基于点的表面几何建模过程。
　　3.1 数据组织
　　密集的采样点模型数据量是海量数据，一个中小城市级别的数据量超过100G，这些海量数据的场景显示一般采用八叉树进行管理，因此在进行场景重构前，要将场景的所有数据按层次关系进行重新组织，这样在动态场景重构时可以以较小的时间代价和较低的内存要求实现。当然在数据组织时要根据具体条件采用一些技术策略：虚拟内存、文件内存映射、动态数据装载等等。
　　一个的数据组织策略决定场景重构的效率。
　　3.2 去噪
　　在由深度扫描仪或采用基于图象的重建方法获取采样点模型表面包含有许多噪声，通过低通滤波技术可以减少一部分噪声。一种有效的方法是通过将采样点模型表面先分成块，然后对每一块通过局部高度场逼近进行重采样，从而把基于傅立叶的光谱分析方法应用于采样点几何进行光谱分析和滤波，达到去噪的目的。另一方法是基于双边滤波函数的去噪方法，采用双边滤波函数进行去噪最早被用在图象信息处理领域，后来被拓展到用于二维流形表面上。虽然这种方法是针对网格模型表面提出来的，但同样也适用于点采样模型表面。该方法在对模型表面进行去噪的同时，还能进行有效的特征保持[2]。
　　3.3 补洞
　　由三维扫描仪对实体模型表面进行扫描时，常常由于模型表面的自遮挡以及镜面材料等原因，使扫描数据中包含有比测量噪声更多的人工痕迹。如：大块的空隙或采样不足，这就需要填补空洞。一种方法是对区域范围数据使用曲面拟合，然后基于曲面重建的方法对采样不足的数据模型进行内插修补。另一种方法是基于上下文的采样点模型表面补洞方法，这种方法是基于邻域相似的原则，在采样点模型的其它地方寻找与空洞周围匹配程度最高的采样点几何块作为填补空洞的几何块，这种补洞方法获得很好的效果，避免了因过分光滑而产生的表面失真。
　　3.4 简化
　　我们在采样时尽可能捕捉现实世界中的物体表面的细节，最终获取的数据模型通常高度复杂；但为了使数据模型的复杂度适合于处理，又必须对数据模型进行简化。一种简化方法是与网格有关的聚类方法（顶点聚类、使用二次误差的累进删除顶点和模拟粒子的重新网格化）应用到采样点模型表面上，取得了与网格模型表面相同的简化效果，其中累进删除的方法给出了很好的简化结果；第二种基于模拟粒子的方法通过叠代地施加点的斥力可以使点的分布均匀化。第三种方法是对每个输入采样点的splat面元在预定误差允许范围内进行邻域生长，形成一个较大的面元，然后从这组后生成的面元（splats）集中，采用贪婪的方法选出一组完全覆盖输入几何表面的子集；最后，采用类似于基于斥力的粒子系统的优化形式对这些被选中的面元进行全局优化以改正splat的分布。
　　3.5 表面着色
　　表面着色就是对采样点进行颜色赋值和颜色编辑，纹理映射、颜色赋值、光照处理等等。由于系统中采样点元既能用来表达模型表面的位置，又能用来表达表面材料属性或纹理，因此，这些值可以很容易地被逐个修改[3]。
　　一种表面着色的最常用方法是采用同步图片纹理映射，通过摄影共线方程和特征匹配，建立影射图片与采样点集之间的空间关系，根据这个空间关系将纹理图片的颜色赋值到采样点，实现采样点的表面着色。另一种方法是根据采样点的位置、法向量和材质，计算出采样点的光照属性，实现采样点的表面着色。
　　对于具有几何位置、法向量和外表属性的采样点模型表面，由于采样点元将这些属性联系在一起，从而大大简化了这些画图工具的使用。
　　4 场景显示
　　基于点的模型数据量巨大，由于要求实时交互，而计算机显示分辨率有限，基于显示器分辨率的点模型快速显示方法，是我们进行场景显示研究采用的方法。显示步骤如下：
　　1、视锥体计算。根据当前的控制视点位置、观测场景范围，计算视锥的位置与向。
　　2、数据节点投影计算。根据当前视锥体和前面建立的八叉树数据结构，将节点数据范围投影到屏幕上，判断这些节点是否是在屏幕显示区域范围之内，并标识这些节点的状态，计算屏幕投影范围和节点数据量之间比率，并由此计算节点的数据抽取率。
　　3、数据读取。将标识为落在屏幕上的节点，按照节点的数据抽取率从文件、数据库中读取相应的数据，并再对这些数据进行重新组织。
　　4、数据显示。使用OpenGL对数据点进行显示，在显示时要处理点的大小、方向、光照、纹理、颜色等等要素。
　　由于屏幕分辨率有限，在满足图形显示的要求的情况下，对于比较大的数据量的情况下，尽量抽虚数据，减少数据显示的点的数量,同时在绘制策略上，尽量采用GPU进行硬件加速。

显示流程框图

不同显示点元显示

　　5 结束语
　　随着三维数字相机、三维激光扫描系统等数据获取硬件设备的发展和摄影测量技术的深入应用，三维点采样技术越来越多在数据采集中应用，基于采样点元作为实体模型基本的造型和绘制元素已经受到图形学界越来越多的关注。作为计算机图形学一个新的研究方向，本文仅对密集点模式的三维场景重构技术进行概略性的论述，对其它基于点的图形学研究起到抛砖引玉作用而已。
　　本人研究的目的，主要是为探索点模式图形学在数字城市管理中的应用，包括点云的数据管理、着色渲染、三维建模等等，这些技术也可以在游戏娱乐、医疗卫生、工程设计、模拟仿真等领域内应用，点元作为一种数码媒体元素具有广阔的应用前景与发展前景。

【参考文献】
[1] 苗兰芳，点模型的表面几何建模和绘制博士论文，浙江大学应用数学系.2005.12.
[2] Weyrich1. Post-processing of Scanned 3D Surface DataIn: Proc. of Symp. on Point-Based Graphics 2004:1-10
[3] Matthias Zwicker.An Interactive System for Point-Based Surface EditingIn: Proc. of Symp. on Point-Based Graphics 2004:5-7