对实时图形处理关键技术的研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇对实时图形处理关键技术的研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：如何快速地传输和操作由“二维折线集、三角网格和点”表示的几何模型是实时图形处理的主要任务。该文以实时图形处理关键技术为切入点，分别分析了几何压缩理论与GPU三角网格数据结构理论，并在存储、传输以及绘制等方面提出提高图形效率的举措，基于扇形带的三角网格拓扑关系表示方法、基于广义三角形带的三角网格数据压缩和多分辨率表示方法以及基于KD-树的点模型各向异性量化方法来增强图形处理实时性。
关键词：图形处理 实时性 关键技术
中图分类号：TP391.41 文献标识码：A 文章编号：1672-3791（2017）04（b）-0018-02
自19世纪60年代，美国麻省理工学院的Iven Sutheralnd教授首先提出了交互式计算机图形学（Computer Graphics）概念。计算机图形学的特点之一是广泛地使用二维和三维几何数据来描述几何模型。在实际应用中，随着计算机图形学及其相关理论与技术的发展，模型的复杂程度不断提高，所使用的几何数据的规模急剧增长，迫切需要一些高效的算法来进行图形处理。
1 实时图形处理关键技术的基本概况
1.1 几何压缩理论
几何压缩主要是运用在图形处理器没有足够大的内存装载巨大的模型时，或者运用在因存在数据传输瓶颈而不能进行图形处理时。图形处理模型变得愈加复杂，这使得存储、处理模型所需的内存和辅助外存代价极大地增加了。网络设计、网络游戏、VR虚拟现实等互连网应用都需要传输几何模型，但是现有的网络带宽使图形处理模型的效率受到了严重限制。在进行几何压缩时会经过三个必要步骤即量化、几何编码以及数据压缩。量化是首要步骤，三个浮点数描述的是三维几何模型的顶点坐标，但数据压缩过程中确定浮点数颇为不易。几何压缩的量化就是将浮点数作为整数进行形式表达，形成一个整数坐标表达式。为满足人类视觉的精度要求，以10或12比特单位来量化一个坐标。运用这种表达式，30或36个单位就可以表达一个顶点位置。上述的这种量化方法，虽然将坐标的浮点数或对应的频域参数量化到了整数网格中，但这种方式没有将数值表达精度和误差划入考虑范围，这导致了浮点数在量化过程中会出现不可避免的数值损耗。针对这一难题，学者Martin Isenburg等人提出了完全无损的浮点数压缩方法。这种方法首先对浮点坐标进行初步量化，运用预测机制求出坐标的预测值，将预测值和实际的浮点数在符号、指数、尾数方面进行对比，最后运用上下文算术编码压缩差值，这可以有效的避免浮点数压缩过程中产生的损耗而提高几何压缩的精确性。几何编码则是几何压缩中最重要的环节，浮点数坐标被量化后，就进入了几何编码操作环节。具体做法是按照一定形式组织模型的顶点，尽可能减少顶点几何表达的冗余，为后续的数据压缩处理提供便利。几何压缩的最后环节是进行数据压缩，为了达到几何编码稻菸匏鸷牡哪康模进一步提高几何压缩算法是必经之路。无损编码和嫡编码是几何压缩的典型算法。算术编码则是效率最高的嫡编码方式，这种方式可以最大程度的减少信息冗余。
1.2 GPU（图形处理单元）三角网格数据结构
在提出几何压缩的概念前，图形标准GL（图形库）和OpenGL（开放图形库）中就开始运用三角形带压缩方法。Hamiltonian三角剖分可以描述为广义三角形带，顺序三角剖分可以描述为顺序三角形带，三角形带的三角网格可以用三角剖分来描述。在图形处理单元三角网格数据结构理论中有诸多学者对其进行讨论。学者Euler提出“三角网格中顶点数量是三角形的数量的1/2，在这种情况下一条广义三角形带上的每个顶点都将被重复传输，这大幅度的增加了传输的冗余量。广义三角形带中SWAP命令编码得到支持，是基于一端设置三个顶点缓冲区，其中任意两个缓冲区的内容都可以随意交换。如果一个广义三角形带上有n个顶点则可以形成n-2个三角形。学者Evans等人在SGI（硅图）算法的基础上成功运用动态三角化将顶点传输降低至2.5次。硅图方法是目前最好的几何压缩算法之一，它是根据开放图形库标准，将图新处理单元一端的顶点缓冲区大小设置为2，顶点在出现顺序三角形带会被重复传输。如果出现一个广义三角形带，同时满足包含一个函数命令的条件，那么顶点被传输两次的数量为1。还有学者基于广义三角形网格数据结构进一步降低顶点的重复传输。以这种方法在贪婪算法的基础上又进一步缩小了三角形带的数量，这种方法将图形处理单元一端设置为具有16个顶点的缓冲区，这大幅度降低了定点传输的数量，但如何根据顶点缓冲区的大小来划分广义三角形网的相应算法还没有被公布，也未被证明。
2 实时图形处理的关键技术分析
2.1 基于扇形带的三角网格拓扑关系表示方法
旧有的图形处理是使简单网格包含一个顶点的扇形与圆拓扑相等，三角网格分解出数个连续的扇形带，相邻扇形通过连接三角形的方式相连。这种形态的扇形描述出的中心顶点和边界顶点关系，不可避免的会使每个三角形都被重复描述三次，由此产生的冗余量可想而知。基于扇形带的三角网格拓扑关系表示方法运用区域增长原理构建扇形带，扇形带的首个扇形不连接三角形，每个扇形带中至少包含一个三角形，扇形带中仅有未被处理的三角形。三角形的个数被定义为扇形的价。将不含三角形的扇形价设置为零。基于扇形带的三角网格拓扑关系表示方法的算法如下所述，小数点后七位的浮点数决定空间三维坐标，空间三维坐标决定点位置，三个点位置决定一个三角形面，这种方法存储量大。在实践过程中会先将点存储于vertex数组下，点用索引值来替换。这种算法通过理清三角形面和点的拓扑关系，对最大潜在扇形进行价的计算并确定中心顶点，再运用区域增长原理，从中心顶点和包含它的三角形出发，逐步计算出所有新点和由它们连接成的扇形直到价变成零。这种方法下计算出的扇形顶点避免了后续扇形带的计算，从而降低了冗余量。计算得出的扇形点以opengl（开放图形库）支持的格式存在于mystack文件中。需要特别说明的是，扇形带总会遗漏一部分三角形，这部分三角形在最后会显示为价“2”，最终计算出的由网格组成的扇形存储数据会包含一部分内容显示为价“2”，这说明该网格扇形带中包含单个三角形，所有均支持开放图形库格式。这种基于扇形带的三角网格拓扑关系表示方法考虑到基于三角网格拓扑关系进行图形处理压缩，并充分运用了区域增长算法理论。以扇形带中三角形的相邻关系为切入点，对网格结构的三角形几何信息进行预测编码。扇形带的结构与目前图形处理单元的结构相宜，所以可以提高图形处理的实时性。
2.2 基于广义三角形带的三角网格数据压缩和多分辨率表示方法
广义三角形带指的是满足Hamiltonian（哈密尔顿）剖分条件的三角形集合。如果一个三角剖分对偶图是哈密尔顿通路或者回路，那么我们称这样的三角剖分为哈密尔顿三角剖分。广义三角形带可以利用图形处理单元结构特点提高处理效率，但不是所有三角网格都可以被描述成广义三角形带。举例说明，三角网格通常被表现为k个广义三角形带集合，三角形数量为m时定点数量为m+2k，每个顶点传输次数为2+4klm。在图形处理单元一端设置适当的缓冲区可以降低顶点被重复传输的次数，但固定大小的缓冲区在实际操作中受制于网格多样性特征而不能发挥效用，除此之外，过大的缓冲区也会导致顶点检索效率的下降。随着图形处理单元技术不断革新，显存与图形处理单元之间的传输带宽达到35 GB/s，传统缓冲区衍生出读写功能并伴随着显存容量的显著增加。除此之外，运用FIFO（先进先出队列）这样的顺序读写结构可以显著提高缓冲区数据的读写速率。基于广义三角形带的三角网格数据压缩和多分辨率表示方法利图形理单元一端的显示缓冲区作为缓存，使得顶点数据的重复传输和存储问题得到解决，同时运用先进先出队列提高缓冲区数据的读写效率，创新性地构造广义三角形带的区域增长算法，保证缓冲区只需要对公共顶点进行存储。
2.3 基于KD-树的点模型各向异性量化方法
如前文所述，量化是几何信息压缩的前提，以点模型为常用项的数据结构中，以空间分割的数据结构为基础，例如八叉树和KD-树，其中就包含了量化信息，几何信息压缩率通过充分利用这些信息得以提高。学者Botsch等人利用空间分割八叉树描述点模型，点的位置信息隐含在节点的层次中，每个节点代表一个8比特的编码，应用在二维流形体的表面上，这一方法使每个点的几何位置平均只需要8/3比特。节点的半径信息可以通过编码间接计算，因此不需要额外储存。学者Botsch等人在工作中使用的是各向同性的量化。各向同性的量化指的是采样点的坐标值x，y和z分量的精度相同。与之相对应的各向异性的量化则是采样点的坐标值x，y和z分量的精度不相同。各向异性的量化沿着坐标轴方向对空间进行的分割是均匀而不同步的。这意味着进行不同精度的量化，采样点的三个坐标分量的比特数可以依照采样点的分布而变化，使得冗余量大幅度下降。基于KD-树的点模型各向异性量化方法就是通过对采样点坐标分量的异性量化来降低集中点的数量，以达到点和多边形交叠显示的目的。利用节点易于将KD-树序列化，可以通过GPU进行解码从而使解码负荷下降。利用空间分割KD-树量化采样点的位置坐标这一各向异性的量化，在保持显示精度不变的前提下，降低采样点数量，并对数据进行压缩。通过引入节点边界盒的可见编码，运用十一位二进制数字对节点对应的几何坐标、法向量和节点尺寸等数据进行表达，使得模型数据量得到显著降低，同时也提高了图形处理的实时性。
3 结语
实时图形处理关键技术的研究在互联网高速发展的今天具有重要意义，作为图形处理的理论基础――几何压缩理论和图形处理单元三角网格数据结构毫无疑问地从诞生发展到现今，都在科学探索、工程设计、机械制造、模拟仿真、医药卫生等众多领域占据者重要地位，被广泛应用于处理计算机图形学以及相关领域中的三维几何数据，以达到完成和实现诸多成果的目的。本文在梳理几何压缩理论和图形处理单元三角网格数据结构相关概念后，探讨了图形处理中的关键技术：基于扇形带的三角网格拓扑关系表示方法，基于广义三角形带的三角网格数据压缩和多分辨率表示方法以及基于KD-树的点模型各向异性量化方法，通过对关键技术的创新应用探索以求实现图形处理实时性的提高。
参考文献
[1] 刘新国.三维几何压缩[D].杭州：浙江大学CAD&CD国家重点实验室，2001.
[2] 赵宇.三角网格模型简化算法的研究与实现[D].沈阳工业大学，2010.