基于GPU的多片元效果的高效绘制

现代GPU的图形绘制管线一般基于扫描线转换算法。模型中的三角面片经过光栅化后投影到屏幕上，在投影区域的各像素位置分别生成一个对应的基本处理单位，称之为片元。在光栅化过程中，当场景中的物体互相遮挡时，相应像素位置会产生多个片元与之对应。一般图形应用只需处理视点所能直接看到的表面，即每个像素只需要保留离视点最近或最远的片元信息，但是有一些绘制效果需要同时处理同一像素位置对应的多个片元，这些特殊的效果通常称为多片元效果，包括顺序独立的透明现象、半透明现象、体绘制以及折射等。然而，现有GPU只针对不透明物体的绘制进行了硬件层面的优化，使得光栅化后每个象素位置只保留最近或最远的片元，其余都在生成最终图像时被抛弃，所以目前多片元效果的绘制需要重复光栅化整个场景多遍，才可以收集到每个像素对应的所有片元。当场景规模较小时算法性能较高，但对于大型复杂场景来说，模型的多次顶点变换将成为绘制瓶颈，导致算法效率下降，因而难以在交互式应用中广泛使用。 针对这个问题，本文提出一种基于桶排序的高效深度剥离算法，将GPU上的多绘制目标缓存作为桶数组，采用桶排序原理以及最大/最小融合模式来收集投影到同一个像素上的多个片元并按深度排序，最后在后处理中再对场景进行延迟着色以绘制多片元效果。当发生桶内片元冲突时可以采用多遍绘制或者自适应划分的方式来降低片元冲突概率，以进一步提高绘制的准确性。针对透明现象的绘制，提出一种基于桶内动态融合的改进算法，采用并发读写的方法逐一融合落入同一个桶内的所有片元，并在后处理中按从前向后的顺序融合各个桶内的颜色值。由于同时发生桶内片元冲突和读写冲突的概率非常小，因而可以进一步提高绘制结果的准确性。实验结果表明，基于桶排序的深度剥离算法可以高效地处理大型场景多片元效果的绘制，同时生成与真实结果非常相近的绘制效果。 针对传统图形管线的不足之处，本文进一步设计并实现了CUDA渲染器：第一个可以在当前图形硬件上运行的全线可编程的图形管线系统，并基于该框架设计了两种新的透明现象的高效单遍绘制策略：第一种策略称之为多级深度测试策略，该策略利用了CUDA 的原子操作符atomicMin，可以在单遍绘制中动态收集所有片元并排序；第二种策略称之为固定数组缓存策略，该策略利用CUDA 的原子操作符atomicInc，可以在单遍绘制中按光栅化顺序收集所有的片元并在后处理中排序。实验结果表明，基于CUDA渲染器的这两种片元收集策略可以在单遍场景遍历中高效地绘制多片元效果，同时生成与真实结果非常相近的绘制效果。 未来的工作方向在于进一步完善基于桶排序的深度剥离算法，设计更加完善的深度区间划分方式，使得桶数组可以与片元一一对应，以完全消除桶内片元冲突。此外，可以进一步完善CUDA渲染器，使其可以更高效地处理遮挡剔除以及反走样等其它经典图形问题。

基于GPU的球面深度图实时绘制

提出了一种GPU加速的实时基于图像的绘制算法.该算法利用极坐标系生成对物体全方位均匀采样的球面深度图像;然后根据推导的两个预变换公式将单幅球面深度图像预变换到物体包围球的一个与视点相关的切平面上,以生成中间图像;再利用纹理映射生成最终目标图像.利用现代图形硬件的可编程性和并行性,将预变换移植到Vertex Shader来加快绘制速度;利用硬件的光栅化功能来完成图像的插值,以得到连续无洞的结果图像.此外,还在Pixel Shader上进行逐像素的光照以及环境映射的计算,生成高质量的光照效果.最终,文章解决了算法的视点受限问题,并设计了一种动态LOD(Level of Details)算法,实现了一个实时漫游系统,保持了物体间正确的遮挡关系.

基于GPU的近似软影实时绘制

通过对阴影图算法进行扩展,提出一种完全基于GPU的近似软影实时绘制算法,它是一种3遍算法:第一遍从光源中心计算场景的深度图;第二遍采用几何着色器提取物体的轮廓边,同时在轮廓边上生成新的几何图元,利用硬件自动插值功能向外绘制线性近似半影图,并根据第一遍得到的深度图在像素着色器中对背面轮廓形成的半影区进行剔除;对于重叠的半影区设定片元的伪深度值,利用硬件进行自动融合.第三遍分别查询深度图和半影图,确定场景的本影区以及半影区中像素的亮度,从而得到面光源照射下场景的近似软影效果.

HFFT算法的大规模集群性能评估及基于CUDA的并行化探索

近些年来，随着计算机硬件技术的高速发展，大规模并行集群系统被越来越多地用于各种科研应用等活动中，而随着多核CPU芯片的技术成熟，多核集群系统对于科学计算的处理能力得到了空前的提高，如何对科学计算中海量数据进行高效地并行计算，评估影响算法性能的相应因素，成为了一个很重要的研究方向。 快速傅立叶变换作为上个世纪公认的最重要的基础算法之一，在包括大规模科学计算处理，数字信号处理，图形图像仿真等众多领域有着广泛的应用，对此，本文结合了2008年中国最快的超级计算机曙光5000A与大规模非规则区域上的快速傅立叶变换算法，深入研究分析了该算法应用在超大规模多核并行环境下的可扩展性测试及影响性能的因素。测试结果表明，该算法在现有的超大规模并行环境下具有较好的性能，在曙光5000A上，算法在8192核的加速比达到了277倍。 本文的另一部分研究工作集中在探索现有HFFT算法在GPGPU上的并行化应用。GPU在处理能力和存储器带宽上相对CPU有明显优势，在成本和功耗上也不需要付出太大代价，这从而为并行数据处理问题提供了新的解决方案。由于图形渲染的高度并行性，使得GPU可以通过增加并行处理单元和存储器控制单元的方式提高处理能力和存储器带宽。 在实际应用中，Nvidia公司的CUDA是用于GPU计算的并行开发环境，是一个全新的软硬件架构，这个架构可以使用GPU来解决商业、工业以及科学方面的复杂计算问题。CUDA是一个完整的GPGPU解决方案，它提供了直接访问硬件的接口。由于目前GPU已在科研领域中得到广泛研究，为了利用GPU的并行数据处理能力，本文探索了一种通过GPU计算提高现有HFFT算法执行速度的途径。之后，本文对CUDA并行算法进行了实际测试，实验结果表明，GPU对并行FFT部分具有20%的加速比，而除去I/O传输后，程序的加速比是34.4倍。

超大规模地形场景的高性能漫游

超大规模地形场景包含大量的几何和纹理数据，无法一次性载入内存，并具有极高的复杂度，因而无法进行实时绘制．提出一种高性能的外存地形场蒂实时漫游技术．该方法使用离散层次细节技术并结合视点相关的动态连续层次细节选择和过渡．算法为地表的简化提出一种新的基于受限法向锥的误差计算方法，使得模型简化具有轮廓保持和光照保持特性．当生成网格包含三角形数目相当时，该方法比传统的基于几何误差的简化更加符合漫游时视觉的感知规律．场景简化过程中提取出的潜在轮廓特征可以通过巧妙地构建漫游时视线方向上的增量地平线来随时更新场蒂不同部分的可见性信息，并以此控制无用数据页面的载入和无效场景部分的绘制，提高绘制速度．漫游系统采用多线程技术．使CPU、GPU、I／O三者的效率得到充分发挥．并可实时生成具有光照和阴影效果的漫游图像．

基于Lattice Boltzmann模型的液-液混合流模拟

引入了一种二元Lattice Boltzmann Model(LBM),实现了两种液体组成的混合流的模拟.不同于其它的类似模型,它区分考虑了流体的粘性和扩散特性,可以很容易地模拟各种互溶或者不互溶的混合流现象.此外,由于LBM的运算大都是线性的局部运算,这使得它很容易在可编程图形处理器(Graphics Process Unit,GPU)上进行加速,从而进行实时模拟.给出了若干二元混合流的模拟结果.

基于Gabor小波的着色及纹理合成算法

着色和纹理合成是图形图像中的两类基本研究课题。前者需根据用户定义的彩色笔触信息，自动对黑白照片、电影或者漫画染上颜色；后者则需根据用户输入的样本纹理，经计算得出与样本纹理视觉上近似的结果纹理。这两类课题都有广泛的应用背景。如着色常常用于给经典的黑白电影或者照片自动上色，解决现在的染色工序中存在的需要大量人工交互的难题；而纹理合成常用于电影和电子游戏的地形地貌、织物、头发等等纹理的自动生成。 这两大类问题都需要分析纹理特征，并且依赖于分析结果的准确性。Gabor小波滤波器与人眼的视觉感受野相当吻合，用它来分析纹理得到的结果比较精确。鉴于此，本文把Gabor小波应用到了着色问题和纹理合成中。对于着色问题，本文用基于Gabor小波的特征向量重新定义邻居关系，然后用最优化方法迭代地对照片和卡通染色。相比以往的算法，本算法具有用户交互少、效果好、算法简单稳健的优点，并且算法允许用户逐步地添加色彩细节。对于纹理合成，本文用基于Gabor小波的特征向量来预计算K-Coherence候选集，提高了K-Coherence算法的准确性，从而改进了纹理合成的最终效果。 本文提出的算法是天然并行的，因而可利用GPU加速，做到实时计算。

面向交互应用的真实感与抽象化绘制技术研究

绘制技术是计算机图形学的关键领域，有真实感与非真实感两大分支。真实感绘制生成高度逼真的画面。非真实感绘制产生抽象和艺术两种效果，其中抽象化图像能够提高人们的视觉沟通效率。由于绘制所涵盖的内容非常广泛，本文主要针对真实感绘制技术以及非真实感绘制中的抽象化技术，研究如何使这些技术满足交互式应用的需求。交互式绘制在工业界和日常生活中有很多重要的应用场合，如工程与艺术设计、虚拟手术、教学辅助等等。交互式系统的响应时间必须足够短，使得用户可以连续地观察并进行交互操作，还必须提供给用户最大的操作自由。 然而，绘制算法的运行速度、画面质量和使用的灵活程度是互相冲突的指标。本文提出一些有效的方法，以使这三个目标达到较好的折衷。这些方法如下： 1) 提出一项可支持近距离点光源、材质和视点同时变化的全局光照计算技术。在对光的传播过程的模拟中，我们利用光能分布在时间上和空间上的相关性，将相邻的采样点进行聚类，并在相邻的帧之间对聚类进行渐进式调整。使用二叉树来组织聚类划分，把复杂的间接光照问题化解成了简单的累加及少量的合并与分裂操作，方便地在GPU上并行执行。这样就实现了交互式重光照，并支持局部光设计与材质设计。 2) 提出一项基于中介面的光线跟踪新算法，可以交互式地渲染动态场景的反射、折射和阴影效果。中介面分布在场景中，以记录不同方向的光线将要相交的几何面片。利用这些中介面，光线跟踪算法中查找光线的相交面片这一相当耗时的过程可以通过图形处理器（GPU）上的纹理查询等简单操作来高效实现，从而极大地提高了绘制速度。 3) 提出一个图像序列的自动抽象化计算框架，可同时提高图像和视频的可压缩性和可理解性，以满足实时视频通信的应用需求。该框架以心理学研究中关于人的视觉感知规律为指导，用一个非线性扩散算法来突出对人眼最为敏感的结构信号并减弱无关的纹理细节，从而提高了观察者的理解效率和视频的传输效率。对于非线性扩散的具体实现，本文提出了一个时空域上的改进的双边滤波器和一个基于GPU的交互式均值移动算法，供用户选择，以在速度和质量之间权衡。 4) 提出一项纹理合成的加速方法，可以应用到图像类推算法中以实现交互式的抽象化绘制。我们通过生成并优化纹理块的邻接集合，来节省纹理合成中大量的相似性度量计算，从而减少匹配冲突，有效地提高了合成的效率。特别是，该方法可以交互式地合成大纹理，这是已有合成方法所难以达到的。 通过上述方案，本文使真实感与抽象化绘制技术能够以更快的速度生成令人满意的结果，给人们带来或者高逼真的或者有助于沟通的视觉体验，且具有良好的操作自由。

伪柔和阴影算法的研究

在计算机图形学领域，阴影的绘制一直是一个热点的研究内容，它对增强场景的真实感有着非常重要的意义。完全物理正确的柔和阴影绘制通常需要耗费大量的时间，于是研究者们提出了各种阴影的近似方法。 本文首先对阴影绘制算法的研究发展历程作了概要性的介绍，特别针对近几年国内外提出的伪柔和阴影算法做了详细的介绍和分析。这些算法主要是根据点光源得到的阴影图[1]和轮廓边进行近似软影绘制的算法，不仅绘制效率高，而且画面真实感比较强。 随着GPU的不断发展，其强大的并行计算能力以及新的可编程着色器，特别是几何着色器[2]的出现，使得基于阴影图的阴影绘制算法中可以加入和场景几何相关的一些计算。本文提出了一个深度剥离[3]和GPU相结合的实时近似软影绘制算法，该算法利用了GPU强大的可编程能力，利用场景物体轮廓信息生成半影图，以此得到伪柔和阴影。实验结果表明本算法是可行的。

阴影实时绘制技术研究

阴影是自然界中一种普遍存在的自然现象，它能够提供场景数据之外的感知信息，因此阴影的实时绘制是真实感技术研究的主要内容之一。本文围绕阴影的实时绘制技术这一主题展开，主要研究内容包括以下几个方面： （1）预滤波阴影贴图反走样技术研究 方差阴影贴图算法是一种基于概率方法的预滤波算法，它本身存在着比较严重的光渗现象。我们采用高次幂函数对深度进行非线性映射，按照这一深度根据方差阴影贴图算法求得一个可见性数值，并与原始的方法求得的可见性数值求取一个最小值，作为最终的可见性，从而能够很好地消除光渗现象。同时，我们针对指数阴影贴图算法的不稳定性，将其与方差阴影贴图算法相结合，采用混合的方法消除二者存在的缺陷。 （2）基于GPU的近似软影绘制 通过对阴影图算法进行扩展，提出了一种完全基于GPU的近似软影实时绘制算法。第一遍与传统的阴影图算法类似，从光源中心计算场景的深度图。第二遍采用几何着色器提取物体的轮廓边，同时在轮廓边上生成新的几何图元，利用硬件自动插值功能，向外绘制线性近似半影图，并根据第一遍得到的深度图在像素着色器中对背面轮廓形成的半影区进行剔除；对于重叠的半影区，通过设定片元的伪深度值利用硬件进行自动融合；这一遍是完全在GPU中运行的，与其它方法不同的是我们只需要一遍绘制即可得到近似半影区纹理。第三遍分别查询深度图和半影图，以确定场景的本影区以及半影区中像素的亮度，从而得到面光源照射下场景的近似软影效果。 （3）基于预计算辐射率传输的近似软影绘制 基于预计算辐射率传输的方法，提出了一种基于圆盘近似的全动态场景柔和阴影实时绘制算法。该方法首先采用圆盘对物体表面进行近似，对每个圆盘形成的遮挡使用椭圆遮挡域表示，预计算过程中根据每个椭圆遮挡域参数进行采样并用球面调和系数表示，同时将其转换为对数，对采样数据采用主元分析方法进行压缩；在绘制的过程中，根据圆盘的法线、半径以及和阴影接收点之间的相对位置确定其椭圆遮挡域的值，然后采用球面调和指数算法进行累积。该方法将圆盘近似算法和球面调和指数算法相结合，能够灵活地描述柔性物体以及较薄的物体形成的柔和阴影。 （4）近似全局光照算法研究 提出了一种混合的近似全局光照算法，对原始模型采用卷积软影图算法计算直接光照，而间接光照采用简化模型计算。在直接光照计算过程中同时生成光源视点的场景的颜色、法线以及世界坐标位置纹理，利用准随机采样的方法从这三幅纹理中获得间接光照采样点，称之为像素光源，然后利用抛物面阴影贴图算法对简化模型计算间接光照；最后将直接光照和间接光照融合获得最终结果。为了进一步提高精确性，仅用简化模型生成阴影贴图，间接光照绘制的过程中采用Deferred Shading的方式进行计算，将视域中可见像素的位置和法线保存在纹理中，间接光照计算直接对纹理中的像素进行。该方法能够较好地处理动态场景的近似全局光照效果。

大规模复杂自然场景的时变模拟研究

大规模复杂自然场景真实感生成一直是计算机图形学的难点和热点之一，而用计算机模拟物体风化/老化/枯萎等现象是真实感图形学的新兴热点研究内容。上述两项技术可成功应用于包括计算机动画、虚拟现实、电影特效和数字游戏等方面。本文对这两个领域中的问题进行了研究与探讨，并取得了研究成果。 自然物体具有丰富复杂的细节，并且数据量很大，其在计算机中的真实感表示一直是图形学中一个富有挑战性的问题。随着研究与应用的深入，人们已不再仅仅满足于自然物体的静态真实感效果，而更加关注于自然场景中的动态时变过程，以及所形成的自然现象的整体效果。对于自然物体会发生的风化/老化/枯萎等现象进行时变模拟可以增强已有结果的真实感。本文即针对大规模自然场景中复杂物体的时变模拟进行了研究，提出了真实感表示、时变模型以及加速绘制等方面的一系列解决方法。这些方法与技术为真实感模拟自然物体的时变现象创造了条件，具有很强的实用价值。本文的主要工作和贡献如下：  首次提出了时变纹元的表示结构，可成功地用于模拟复杂自然物体的风化/枯萎等现象。该结构改进了传统三维纹元，加入时变特性方面的描述信息。时变纹元中记录的纹元变化序列，可有效用于表示自然场景中最重要组成部分──大规模草地的枯萎时变过程。本文使用时间-空间划分树对时变纹元数据进行重新组织及有效压缩。采用这种层次树结构处理的时变纹元，并应用GPU上的光线行进算法进行快速体绘制，最终可得到具有真实感的时变模拟结果。  基于时变纹元的表示结构，提出一种新的模型结构转换机制，使之能够采用物理模型/过程模型对复杂自然物体的动态几何形变进行模拟。纹元的三维阵列结构难以处理物体的个体几何形变，因此本文提出借鉴点模型的转换结构以解决这个问题。本文给出了点模型和纹元的转换规则，可通过计算点模型的动态信息而得到纹元的时变序列。该算法充分结合了纹元结构及点模型的优势，为模拟复杂自然物体的时变现象提供了有效新型方法。  首次提出了γ-ton体跟踪算法，可用于对复杂自然物体的风化现象进行模拟。γ-ton跟踪算法是目前能够有效模拟物体风化现象的通用框架之一，可同时计算物体几何形状和材质随时间变化的情况。但是该方法仅适用于跟踪发生在物体表面的时变现象，而无法处理自然物体体结构中的材质及形状的改变。本文提出的γ-ton体跟踪算法可针对复杂自然物体，模拟其体结构上产生的风化/老化现象，增强了算法的适用性。  首次提出了基于纹元结构的重绘制算法来增强图像及视频中的毛发真实感。该算法采用图像分析方法，将图像中的目标区域进行提取并网格化，生成纹元结构并映射到图像网格之上，通过重绘制算法得到增强毛发感的新图像。本文的算法同样可处理视频，首先计算得到视频关键帧的重绘制结果，然后基于目标区域在时间轴上的匹配情况，从关键帧出发进行前向及后向传递，计算视频中的其余帧的重绘制结果，最终得到毛发感增强的新视频。本文的方法提供了一种能够高效生成具备毛发真实感的图像及视频的新型方法，这对于电影制造业有很高的应用价值。

非真实感绘制中的线绘制技术及其水墨仿真研究

绘画是人类捕捉、记录及表现不同创意目的的行为，是一种在二维的平面上以手工方式描绘自然的艺术。从远古的石洞壁画到现代的各种绘画艺术作品和插图，随着人类历史的进步，绘画一直扮演着传递信息和艺术表达的角色：作为表达场景信息的手段，在照相技术出现之前，手工绘画一直是最好的方法；而另一方面，作为艺术行为，绘画可以表达作者的精神世界和自我风格。 随着计算机技术的出现和发展，计算机绘图逐渐成熟，并形成一门独立学科：计算机图形学。非真实感绘制(Non-Photorealistic Rendering, NPR)作为计算机图形学的热点研究课题最为接近手工绘画，有别于传统计算机图形学，它是涉及计算机艺术、数字图形处理、认知心理学等多领域的交叉研究领域。非真实感绘制的一个重要作用就是将计算机技术和绘画艺术结合起来，自动或交互地生成具有手绘艺术风格的图像。其目的不在于绘制结果的真实感，而在于表现绘画艺术特质、模拟艺术作品等。非真实感绘制往往依据艺术家的视觉感官或为了突出物体某方面性质，会着重强调某一方面细节而忽略一些其他细节信息。 本文围绕非真实感绘制技术，从模拟线绘画和中国水墨绘画两个方向进行研究。以简单的三维网格模型为输入，力求完全自动化地进行实时绘制。本文工作主要分为两部分：实时线绘制技术和二维水墨扩散仿真。 线条绘画，是表达物理场景既简单又实用的绘画手段，线绘制技术也是非真实感绘制领域最重要的研究课题之一。无论是插图还是艺术绘画，线绘制图像都可以完全表达出三维场景的形状信息而不用借助于其他绘画手段。本文首先总结了前人的线绘制算法，并针对视点相关特征线和视点无关特征线的优缺点，提出了一种融合两类特征线优点的特征线新定义。基于该定义，本文算法以模型曲面的微分几何信息为依据，运用基于图像的绘制技术，利用GPU硬件，实时地绘制出风格可控的线绘制图像。 对于种目繁多的艺术流派，目前NPR技术已经实现了多种绘画艺术风格的模拟，如水彩画、铅笔画、钢笔画、油画等等。水墨画是作为中国传统绘画艺术形式，画风朴素抽象，笔划简单但富表现力，是我国优秀的文化传统。对水墨画的仿真模拟，不仅是传承我国优秀文化的一种新方式，同时也是对NPR技术的拓展。由于本文线绘制算法有较好的线宽控制以及内部着色（灰度渐变），在实现上可以很连贯地由线绘制图像扩展到水墨仿真。在水墨扩散模拟阶段，将线绘制结果图像作为输入，通过在二维水墨扩散仿真实现水墨风格的绘制。本文运用流体力学中常用的LB方法，通过研究水墨扩散的各种现象，修改LB方法的D2Q9模型二维网格间的流体迁移运算以及网格的宏观量更新，模拟水墨在宣纸内的流动。由于LB方法具有良好的并行性，故本文仿真算法可以利用GPU的并行计算能力实时地完成绘制。