一种基于GPU实现的自适应八叉树纹理绘画算法

2010-07-07程志全金士尧

图学学报 2010年4期

李航，党岗，程志全，金士尧

（国防科技大学并行与分布处理国防科技重点实验室，湖南长沙 410073）

纹理映射是一种增加多边形模型细节外观的非常有效和高效的技术。但目前广泛使用的2D纹理映射有着很大的局限性，它需要将网格参数化、即分配给每个网格顶点一个2D纹理坐标来完成。通常这一参数化过程是非常困难的，而且会带来扭曲和裂缝，特别是在含有隐含表面、细分表面等的复杂网格上。

与2D纹理相比，3D纹理通过将纹理定义在包围物体的体上来避免2D参数化。3D体纹理的优势在于其纹理坐标能程序化自动产生，而且在任意精度下的采样都是均匀的。其缺点也很明显，占用的内存随着立方体分辨率的提高而急剧增加，在高分辨率的需求下几乎是难以实现的。

八叉树纹理是体纹理的一种变形，它只对体的子集与模型表面相交的那一部分进行存储，形成了一种稀疏纹理，大大节省了存储空间。在GPU上实现八叉树纹理后，通过硬件协助，使纹理的查找速度进一步加快，实时性得到提高。在原有的低分辨率、小内存占用情况下，如果用户想进行高分辨率的绘画，虽然可以将分辨率提高到相应水平来达到目的，但是由于体纹理的特性，内存的需求将上升的非常快！

本文提出了一种基于 GPU加速的、可变局部分辨率的、实现实时绘画的自适应八叉树纹理绘画算法。本文的实现将需要高分辨率的细节绘画部分与其他部分区别对待，只在需要的部位创建高分辨率纹理，进一步节省了存储空间。

在下面的章节中，本文将首先概述相关工作，而后阐述一种新型的自适应八叉树纹理映射机制（第二部分），进而说明其基于GPU实现的方法（第三部分）。在给出实验结果并加以分析（第四部分）后，本文最后对工作进行总结。

1 相关工作

纹理映射一词最早由Catmull[1]提出，其实质是从二维纹理平面到三维模型表面的一个映射。在立体纹理的概念出现后，因为体纹理坐标能自动生成，人们从手工赋予模型坐标的繁琐工作中解脱出来。但用体纹理进行高品质纹理建模将占用大量存储空间，因此3D纹理的发展速度比较缓慢。

八叉树是一种规则的层次数据结构。树的第一个节点即根节点，是一个立方体。每个节点有8个子节点或者没有子节点，且这8个子节点是对父节点的一个2×2×2的规则细分。其中，不含有子节点的叫做叶节点。在一个包含了3D模型的八叉树中，那些包含了模型表面的节点被更细致地划分，而余下的空节点则成为了叶节点。八叉树每个维度每细分一次，其分辨率都将增大到原来的两倍。因此，要达到一个256×256×256的分辨率，总共需要 8层（28=256）。自适应八叉树则是在模型的不同区域有着不同的分辨率或者说树深度，其树深度大的地方能表现更详细、更真实的图像效果。

SIGGRAPH2002会议上David Benson和Joel Davis[2]撰文提出了一种用八叉树实现纹理映射的方法，David DeBry[3]等人的文章也独立发展了一种近似于用八叉树实现纹理映射的方法。到了现在，在GPU上实现八叉树纹理[4]后，八叉树纹理的性能得到了进一步提高。相比体纹理，用八叉树结构来存储纹理时，颜色只存储在物体表面与体相交的地方，因此可以减少内存需求，而且在物体表面的采样也是均匀的。虽然对于大数据量的模型来说，八叉树纹理仍然会因占用了太多存储空间而被限制使用，甚至不可实现，但作为图形硬件上所用的通用数据结构[5]之一，八叉树还是有着很重要的作用和广阔的应用空间。近年针对八叉树的不足，已出现了如分块的混合八叉树[6]、GPU加速的八叉树体绘制[7]等从不同角度对八叉树进行改善的方法。

2 自适应八叉树纹理

指定深度的规则八叉树，其分辨率在用户使用前已经固定下来。现在考虑这样一个问题：低分辨率情况下，在一个全白色的模型上画一个很小的红色点，其尺寸远小于叶节点的尺寸时，会出现什么样的情况。一种可能是在叶节点中进行简单的判断，将这很少量的红色抛弃；还有一种可能是通过线性插值将红色和白色混合在一起，形成粉色；或者干脆将整个叶节点变成了红色。但无论出现哪种情况，都是严重的失真。要保持红色点的细节，只有将该处的八叉树纹理分辨率提高，也即将该处叶节点进行细分，直到新叶节点的大小适合于红色点。

根据不同的细节表现要求，将不同区域的分辨率自动设置成所需的程度，规则八叉树便变为自适应八叉树。

2.1 构建自适应八叉树

先以低分辨率建立一个原始八叉树，即细分所有与物体表面相交的节点，直到叶节点为空或者达到了选择的深度（包含颜色的节点）。最初分辨率在程序中指定，可设为一个较小的值，比如43或83，这样包含颜色信息的叶节点深度只有2或 3。然后根据光标的绘画位置开始构建自适应八叉树并最终上色，伪代码如下所示：

首先获得画笔绘画位置的屏幕坐标，然后参照模型获得物体表面要上色的点的空间坐标，再找出空间坐标位于哪个叶节点，然后递归细分节点；这里利用程序的重复性，在每次细分后再找到要进行下次细分的叶节点，依次循环下去；达到用户指定的分辨率水平后，将叶节点上色。

这样做在达到合适分辨率的同时，还最大限度的节省了存储空间。自适应八叉树的建立过程如图1所示。

图1 框架结构图

2.2 占用存储空间的对比

占用过多的内存是限制3D纹理广泛应用的主要原因。虽然八叉树是一种稀疏的数据结构，八叉树中那些不包含物体表面的节点不需再进行细分，只有与物体表面相交的叶节点中存储了数据，但是要达到和通用的2D纹理同样的效果，仍需要将八叉树纹理的分辨率提到比较高的层次，其存储空间的迅速膨胀依然是个很严重的问题。与此相比，自适应八叉树纹理能较好的缓解内存开销问题。

比较一下体纹理、八叉树纹理和自适应八叉树纹理的存储开销。对于传统的体纹理，当分辨率为256×256×256时，每个体元素中存储一组RGBA 值，占用的空间就是 256×256×256×4B=64M。达到同样的分辨率需要一个深度为 8的八叉树，不妨假设八叉树的每个节点都只有4个子节点和物体的表面相交，另4个子节点为空，那么八叉树中包含的节点数为

每个节点存储8组RGBA值，则占用的存储空间约为 683K。可以看出比起传统的体纹理，八叉树纹理已经节省了大部分存储空间。而对于自适应八叉树纹理，假设最初树深度只有2，考虑两个极端情况：一是在物体表面只画一个分辨率为 256×256的点，另一种是用这样的点画满整个物体表面。容易看出后一种情况就变回到常规的八叉树纹理，无需再算。下面计算第一种情况：初始时，树节点个数为5。每次细分时，一个叶节点下产生8个子叶节点，最后得到的总节点数为5+8×6=53个，占用空间1.7K。那么最大深度为 8的自适应八叉树占用的存储空间就在1.7K到683K之间。对于绘画青花瓷这类只在少数部位有高细节表现的物体来说，使用自适应八叉树来存储纹理将最大限度的节省存储开销。

3 GPU实现

GPU（Graphic Processing Units，图形处理单元）驱动3D图形进入了新的复兴时代。现代的高级编程语言联合难以置信的并行计算能力，可以轻易地完成实时的模糊阴影、精确的照明模型和真实的材质影响。传统上在程序中用语句遍历八叉树进行查找是个比较慢的过程，而在 GPU上实现八叉树后，纹理的查找速度大幅提高，实时绘画才能较好的实现。

在 CPU上实现八叉树的一个很简单的办法是用指针将节点连接在一起，每个节点包含一个指向其子节点的指针数组，叶节点中则只包含数据而没有指针。每个节点包含8个指针，指向其子节点。

在 GPU上实现八叉树与此相似，只是将指针变为了纹理中的索引，索引被编码成RGB值。叶节点的RGB值则干脆直接存储在其父节点的索引中，并用Alpha通道来区分某个子节点中存储的到底是索引还是叶节点的 RGB值。换句话说，节点中存储的要么是用于指向其子节点的RGB值（即索引）、要么就是其叶节点的 RGB值（即数据）。本文的实现同样需要依赖纹理查询(dependent texture lookup)。自适应八叉树和规则八叉树在存储方式和 GPU实现等方面都是类似的，下文中提到的八叉树纹理则泛指包含自适应八叉树纹理在内的一般意义上的八叉树纹理。

3.1 纹理存储

本文采取的方法是把八叉树存储在一个8位的RGBA 3D纹理中，这种纹理叫做间接池。间接池中的最小存储元素叫做单元，每个单元存储一组RGBA值（索引或者数据值）。间接池又被细分为间接栅格，间接栅格是由2×2×2个单元组成的立方体，那么每个间接栅格就表示一个树节点，它对应于CPU实现中每个树节点包含的8个指针。每个间接栅格的单元可以是空的，或者为以下情况之一：

（1）如果相应的子节点为叶节点，则单元中存储的是数据值；

（2）如果相应的子节点为另一个非叶的子节点，则单元中存储的是一个间接栅格的索引。

图2展示了间接池中八叉树的存储结构，第一个间接栅格中的3个有色子块表示存储的是索引，后3个间接栅格的各单元所对应的子节点是叶节点，存储的是数据值。

图2 间接池存储结构示意图

为了清晰起见，在图中将间接栅格分离开来，而在实际的存储结构中间接栅格是连续的。

如果用户想得到256×256×256的分辨率，就要设置间接池中的间接栅格个数为128×128× 128，这样间接池中的单元的分辨率就是(2×128)×(2×128)×(2×128)。

前面已提到，在单元中，数据和子节点索引都是存储为RGB元组的形式。Alpha通道则作为区分单元内容的标志。Alpha=1表明是数据，Alpha=0.5表明是索引，Alpha=0表明是空节点。八叉树的根节点就存储在间接池的（0，0，0）处。

3.2 纹理查找

把八叉树存储在纹理存储器中之后，需要在片段程序中对它进行访问。和标准的3D纹理一样，树把纹理定义在单位立方体中。如果希望获得在树中某点M处存储的纹理值，那么要从树的根节点开始，顺序访问包含M点的节点，直到叶节点为止。

对于某个深度D，完全树会在单位立方体内产生分辨率为 2D×2D×2D的规则栅格。把该栅格叫做深度D栅格，树在深度D的每个节点都对应于该栅格的一个单元，显然M也位于深度为D的被访问节点所对应的单元中。设M在该单元中的相对坐标为(XD，YD，ZD)，该单元在树中的坐标即为被访问节点间接栅格的索引ID，再设间接池中间接栅格的个数为S，用这些参数可得到间接池中的查找坐标

然后得到了间接池中 P点所存储的 RGBA值。根据Alpha通道的值判断，如果子节点是叶节点，将会返回RGB值，否则就表明存储的值是索引，把 RGB值作为该子节点的间接栅格的索引ID+1，并继续查找下一个树深度。图3为树层数为3时的间接池查找过程示意。

树的深度是有一定限制的，对于1024×1024分辨率的显示器来说，深度 10已经是硬件能支持的最大值，因为此时已经达到了像素级水平，再增加深度已经没有意义。

所以每次查找的纹理访问次数也是有限的，对于最大深度为8的自适应八叉树，显然最多只需要8次访问就可以找到间接池中的目标点了。

图3 纹理查找过程

4 实验结果

随着几何体表面积的增加，八叉树的节点数会大幅度增加，占用的存储空间也会越来越多，对于有海量数据的模型来说，八叉树纹理也是不可实现的。所以目前3D纹理主要应用于较小型的物体上。而由于对不同区域采用了不同的分辨率，只占几何体一小部分的高细节部位才需要较多的节点，自适应八叉树纹理能较好的用于部分大型模型。

针对表面积较大的 Mouse模型和表面积较小的Laddy模型，本文的实现对比了使用固定深度的规则八叉树和使用自适应八叉树进行绘画时两者的占用存储空间、建树时间、指定的最大深度等数据，如表1和图4所示。

当树深度指定为9或10时，由于节点数量过于庞大，即使对于表面积较小的Laddy模型，Matt Pharr[4]的实现程序在构建规则八叉树时经过 30多分钟仍未得到结果，而本文的实现在构建自适应八叉树时则不存在这个问题。

此外在树深度较小时，规则八叉树不能进行很理想的细节绘画，因为此时的树节点不能很好的近似匹配物体表面，绘画时的锯齿现象比较严重。

表1 规则八叉树和自适应八叉树的相关数据

5 结论

本文提出了一种 GPU上的自适应八叉树纹理算法：利用自适应八叉树来存储纹理信息，达到在局部进行细节表现的目的，更进一步节省了存储空间；同时经过 GPU加速，实现了细节实时绘画。实验结果表明，使用自适应八叉树纹理，在相同的最大分辨率情况下比规则八叉树纹理占用了更小的存储空间，也可在更高的分辨率水平上进行比较理想的细节绘画，甚至是像素级的逐点绘画。从而，本文改进了八叉树纹理的构建和存储，同时利用了 GPU加速，很大程度上解决了八叉树纹理自适应分辨率的局限，实现了自适应分辨率的实时绘画。

本文提出的这种自适应八叉树纹理绘画算法还有以下几个需要优化的方向：一是刚开始绘画时的延时比较严重，因为在最初开始绘画时要进行适应分辨率的节点细分和新建存储，相当于将最初的构建八叉树纹理的时间分散到绘画步骤中去，虽然极大的节省了最初构建八叉树纹理的时间，但是部分影响到了绘画时的实时性。二是本文的实现依然没有解决模型中非常接近或相交的表面的处理问题，例如皮肤和衣服。