基于虚拟场景的绘制算法★

赵莹，韩燮

(中北大学电子与计算机科学技术学院， 山西 太原 030051)

0 引言

近年来随着计算机图形、图像学技术的发展，虚拟场景的构建已取得了较好的效果，但构建大规模且复杂的虚拟场景仍是耗时费力的工作。针对虚拟场景耗时费力的问题，点绘制技术引起人们的关注，它具有基于几何绘制方式的绘制质量、灵活性和内存需求和基于图像绘制方式的绘制速度。但点绘制仍然存在许多不足之处，考滤到物体还有其它不同的构成形式例如面和体数据，由此可以研究以不同的元素作为绘制的基元，来提高存储效率、绘制性能、绘制质量等，使构建的虚拟场景呈现出更真实的效果。

1 点绘制

基于几何模型的绘制通常把扫描所得的数据生成三角片网格，但当模型高度复杂时此方法就不实用了。基于图像的绘制技术使用图像作为绘制基本元素，这种方法的不足是要占用大量的内存空间，并且与视点相关。综合上述两种技术的优缺点，人们提出了基于点的绘制技术，将点作为绘制的基本元素，摒弃了传统的三角片表示方法，只记录点的信息，这些点又不同于基于图像技术的输入像素，而包含了附加的几何信息，并且点采样与视点无关。

基于点的计算机图形学(Point-Based Graphics，PBG)的一般流程可以概括为点的获取、点的处理与建模、点的绘制3个阶段[1]。首先利用三维扫描设备对物理对象进行数字化采样，得到原始的数据；然后转化为适合于后期处理与造型的表示形式；最后采用合适的绘制方法将模型显示出来。基于点的处理流程如图1所示。

图1 基于点的处理流程

点绘制技术关键工作是由离散点在屏幕上重构没有空洞的连续表面。根据重构表面采用的不同技术,基于点的绘制算法可以分为两大类：图像空间的点绘制算法(表面足迹法)[6]和物体空间的点绘制算法(QSplat)[7]。表面足迹法注重的是绘制的质量，但计算量比较大，导致绘制速度降低。QSplat方法将模型距视点较远的多个点合并为一个点来处理，这样大大提高了绘制效率，但由于没有考虑绘制质量，会在轮廓线区域处产生严重的走样。因此，张龙等在2005年提出了一个针对大规模点模型的实时高质量绘制算法[2]，该算法采用与视点远近相关的关系进行自适应绘制。对于远处的点，将它们“合并”为较大的点，用比较模糊的绘制模式来绘制；对于近处的点，则用比较细致的绘制模式来绘制。在不损失绘制质量的前提下同时也简化了计算，很好地融合了绘制质量和绘制效率。

2 面绘制

面绘制技术实际上是把体数据用一种逼近面形式表示，其基本过程是确定物体的轮廓，并由一系列等值面表示出来，从而进一步由传统的图形学技术进行绘制。由于面绘制的绘制过程中需要构造等值面，生成中间图元，不是直接由体数据上绘制图像，所以面绘制技术又被称为间接体绘制。面绘制有很多种算法，各种算法的不同点在于所采用的物体近似表面的几何单元不同或选择的几何单元尺度不同，典型算法有MC算法(Marching Cubes)、MT算法(Marching Tetrahedral)、剖分立方体法(Dividing Cubes)等[3]。

MC算法是把离散的三维数据场表示转换为等值面的逼近三角面片表示,然后可以利用计算机图形学技术或现有硬件加速技术完成等值面的近似表示。MC算法基本思想是将读入的三维图像看作一个个图层，从相邻两个图层分别取4个像素共8个顶点组成一个立方体，这样就可以把图像分成若干个小立方体。然后比较小立方体的顶点与给定阈值的大小关系，将立方体的顶点以1或0标记，顶点大于阈值为1，小于阈值为0。其中有一部分立方体与阈值所在的等值面是相交的，采用插值计算出立方体边与等值面的交点，然后将交点连接起来以形成三维图形。理论上每个顶点共有2种状态，所以等值面分布总共有256种状态，然而由于立方体的对称性，经过旋转和翻转后只有15种情况。

MC算法步骤如下：

(1)构建索引表，该表指明等值面与体素的哪条边相交，共256种相交关系。

(2)构建体素，从相邻两个层图中取8个像素构成一个体素，如图2所示。

图2 体素

(3)将每个像素与阈值进行比较确定该像素是0还是1，并把这8个像素构成的01串组成一个8位的体素索引表。

(4)用索引值在索引表里查找对应关系，并求出与立方体每条边的交点，交点构成三角形面片。

(5)遍历三维图像的所有体素，重复执行(2)到(4)。

MC算法提供了一种精确定义体素及等值面的生成方法，但也存在许多不足，许多学者对此进行了改进。MC算法是通过阈值分割来提取等值面，阈值分割对边缘特征清晰的物体比较适用，对边缘特征模糊的物体则难以得到较好的效果。针对这个问题可以将目前计算机图形学中比较成熟的图像分割算法进行比较，采用适合的算法作为MC算法的分割算法。另外MC算法的输出是三角形网格，由于数据分布十分密集，由此建立的三维网格数量庞大，因此可以采取有效措施对MC算法输出的模型进行合理的简化，来提高空间和时间的效率。

3 体绘制

实际中有许多场景都不能用简单的面来表示，例如云、雾、水、火等，这些场景形成的数据中并不包含真实面。在这类情况下面绘制技术就不适用了，所以有学者提出了体绘制技术。体绘制是以体素作为基本单元，直接由切片数据集生成三维体的图像，也称为直接体绘制。体绘制技术是一种基于光学映射的方法，这种方法通过模拟光线在物体内部的一系列光学现象，使得到的体绘制图像更具真实感、便于分析。

体绘制过程就是将离散分布的三维数据场，按照一定的规则转换为图形显示设备帧缓存中的二维离散信号。直接体绘制算法很多，根据对空间数据的绘制次序不同主要分为两类：以图像空间为序和以对象空间为序的算法，但是基本步骤大致相同。第一步是获取体数据。根据应用场合，数据的获取方式可以有多种渠道。然后是数据分类。数据分类就是对每个体数据根据其标量值赋予R，G，B，A等光学特性，这个过程将决定哪些体数据可见，哪些不可见。最后是绘制显示。确定视点、投影类型平行或透视、剖面位置等信息，将产生的几何图素和属性转换为可供显示的图像[4]。体绘制算法框架图如图3所示。

图3 体绘制算法框架图

本文介绍一种以图像空间为序的典型算法光线投射法(Raycasting)[5]，它从图像空间的每一个像素出发沿视线方向发出一条射线，这条射线穿过三维数据场，顺着这条射线选择多个等距的采样点，并由距离某一采样点最近的8个数据点的颜色值和不透明度值作三次线性插值，求出该采样点的颜色值和不透明度值。然后再将每条射线上各采样点的颜色值和不透明度值由前向后或由后向前加以合成，即可得到发出该射线的像素点处的颜色值，就可以在屏幕上得到最终的图像[11]。

4 算法比较及实验结果

基于点模型表示与绘制具有拓扑结构简单、绘制体系简单、适于表示表面几何及光照细节比较复杂的模型、适合混合绘制、较少冗余且有硬件支持等优点。自适应绘制算法很好地融合了绘制质量和效率的要求，但仍有待于进一步的研究。

面绘制只适用于绘制表面特征分明的物体，对过渡比较平缓的物体绘制效果不佳，而且面绘制只能显示物质的轮廓信息，内部信息无法保留[8]。面绘制技术有许多应用，如在医学领域中可以用等值面表示，也可以使用等值面产生算法抽取各种人体组织。MC方法具有简单、易实现、速度快等优点。

体绘制在许多应用中能产生高质量的图像，并且已经特别成功地应用在可视化中。与面绘制方法相比，直接体绘制的主要优点是可以表示对象体的内部信息，但计算量大，包括体数据的采样、重构、重采样、组合、绘制等操作。光线投射法优点是图像质量高，缺点是会造成重复计算且内存开销较大[9]。3类绘制方法的优缺点比较如表1所示。

表1 3类绘制方法比较

本文使用基线为12cm，焦距为3.8mm的双目相机拍摄一个比较圆滑的瓶子，获取深度数据，根据不同算法所绘制出的图像如图4所示。

图4 绘制结果

可视化的应用越来越广泛，研究人员也重视起了这方面的研究。虚拟场景的绘制方法有多种，人们可以根据场景和物体的复杂性、光照情况及用户的需求选择适合的绘制算法。随着虚拟现实技术的发展，虚拟场景绘制技术的研究也不断的进步，它的研究已经广泛地应用于虚拟场景的生成、物体表示、虚拟仿真等领域[10]。这些不断增长的应用领域要求我们能够更加深入地研究虚拟场景生成的技术，开发出更加快速、高效的算法。

[1]高秀芬,陈福民.基于点的图形绘制技术[J].计算机工程与应用,2005（9）:20-22.

[2]张龙,董朝,陈为,等.大规模点模型的实时高质量绘制[J].计算机学报,2005,28(2):241-249.

[3]唐占红, 於时才.面绘制三维重建原理及其改进算法研究[J].计算机工程与设计,2009,30(9):2225-2228.

[4]尹学松,张谦,吴国华,等.四种体绘制算法的分析与评价[J]. 计算机工程与应用,2004（16）:97-100.

[5]洪歧,张树生,王静,等.体绘制技术[J].计算机应用研究 ,2004（10）:16-19.

[6]Ren L., Pfister H., Zwicker M.. Object space ewa surface splatting:A hardware accelerated approach to high quality point rendering[J].Computer Graphics Forum,2002,21(3):461-470.

[7]Rusinkiewicz S, Levoy M. Qsplat: A multiresolution point rendering system for large meshes[C].Proceedings of ACM SIGGRAPH.2000:343-352.

[8]张翔,张大志,田金文,等.基于相关性的快速体绘制研究[J].计算机工程与科学,2005,27(2):33-35.

[9]孙薇薇,张桦. 三种体绘制算法的比较[J].天津理工大学学报,2005,21(4):9-11.

[10]全红艳.基于几何与图像结合的虚拟场景绘制技术研究[D].哈尔滨:哈尔滨工业大学,2006.

[11]丁庆木,张虹.图像体绘制算法的分析与评价[J].系统仿真学报,2007,19(4):897-900.