gpu加速物体空间线绘制的通用算法

gpu加速物体空间线绘制的通用算法

线描是一种经典的非现实主义绘画方法，它通过简洁的线条来表达物体的形状特征。作为一种艺术表现形式，线性绘画已经存在了数百年。线条的表现也广泛应用于现实生活中。例如，许多产品的解释使用了许多图纸来解释产品的功能。此外，许多线条也出现在许多图纸和书籍插图中。大多数手稿都是通过线条来表达的。近年来,线绘制成为非真实感图形学以及表意性绘制领域中的一个研究热点,其主要研究如何对输入的三维网格模型自动地抽取特征线,并生成高质量的线绘制结果.人们已提出了许多算法来解决这一问题,这些算法大致可分为物体空间算法与图像空间算法2类.图像空间算法首先通过某种表面绘制方法绘制模型,得到一幅(或多幅)二维图像,然后通过对得到的图像进行某种图像空间的滤波处理,生成线绘制结果.该类算法不需要计算模型表面的各种几何量,计算代价小、容易使用GPU加速、绘制速度较快,并且适用于处理动态变形的几何模型.但是,图像空间算法的鲁棒性不高.由于在生成图像的过程中不可避免地需要进行离散化、颜色值量化等操作,因而生成的线绘制结果常常显得不够连续.图1所示为对一个网格模型由图像空间算法和物体空间算法生成的线绘制结果的对比.其中,图1b与图1c的特征线定义在理论上是一致的,但是图1b在图像空间计算,而图1c在物体空间计算.显然,物体空间算法更加鲁棒,生成的线绘制结果更加光顺、连续.另一方面,图像空间算法得到的线绘制结果没有特征线的几何信息,所以难以生成风格化的线绘制结果.物体空间算法将网格模型看作一个二维流形曲面,将特征线定义为模型表面上满足某种几何特征的极值线.不同的几何特征对应于不同的特征线定义方法,例如常用的脊线与谷线分别表示模型表面最凸和最凹的部位,其在数学上表示为曲率局部最大及局部最小的点组成的特征线.在线绘制中所采用的几何特征定义往往依赖于当前视点,例如轮廓线是满足视线与模型表面相垂直的特征线.其他常用的特征线定义方法,如近似轮廓线、明显的脊线、光极线(photicextremumlines,PEL)、拉普拉斯线等也跟视点位置有关.对于视点相关的特征线定义,当视点发生变化时,特征线的位置同时也发生变化,在绘制时需要重新计算.由于物体空间算法通常要基于离散微分几何原理计算模型各个顶点的高阶导数值,因此计算代价很大.对于复杂的模型,线绘制的速度往往无法达到实时,例如对于具有100万个三角面片的网格模型,显著脊线(apparentridges)与PEL线的绘制速度不到5帧/s.本文提出一种基于GPU的物体空间特征线绘制框架,其中所有物体空间特征线绘制算法都可以利用GPU加速.特别地,本文提出了轮廓线与PEL的GPU加速绘制算法.如图2所示,使用本文提出的GPU算法进行绘制,绘制结果与传统CPU算法生成的结果几乎没有区别,但是绘制速度大大加快.1相关工作1.1图像空间线构成算法图像空间线绘制算法通过对获取或生成的二维图像进行图像处理,从而生成线绘制结果.Buchanan等提出一种称为“边缓存”的数据结构,能够在绘制网格模型时突出显示重要的特征线.Raskar等提出一种“非真实感相机”技术,对同一个场景分别使用不同的闪光灯强度拍摄多幅照片,通过多幅照片的对比,检测照片中深度不连续的区域,从而生成轮廓线绘制的结果.Lee等提出一种基于“抽象光照”的线绘制方法,通过抽象光照明模型生成模型的光照图,在各像素上通过函数拟合计算多种图像空间的特征线.Vergne等提出一种图像空间的模型特征分析方法,通过在图像空间的多次滤波操作得到模型的局部几何特征描述.一般地,图像空间线绘制算法实现简单、效率高,文献已实现了利用GPU加速绘制.本文算法不考虑图像空间算法,而是针对更加鲁棒的物体空间线绘制算法进行设计.1.2模型特征线面向物体空间线绘制算法通过在模型表面定义一个几何特征函数,并根据特征函数计算特征线的空间位置并生成线绘制结果.物体空间线绘制算法需要解决的关键问题是在哪里画线,即特征线如何定义,其归结为特征函数如何定义.典型的特征线定义方法包括:1)轮廓线(contours).法向与视线方向垂直的特征线,包括外轮廓(即侧影轮廓线)与内轮廓.2)近似轮廓线(suggestivecontours).法向与视线点积的局部最小值,是轮廓线的自然扩展.3)高亮线(highlightlines).法向与视线点积的局部最大值.4)显著脊线(apparentridges).在当前视点下模型表面最凸与最凹的部位在数学上定义为视点相关曲率的局部最大或最小值.5)PEL.将Canny图像边缘检测算子转换到物体空间计算得到的特征线.6)拉普拉斯线.将LoG图像边缘检测算子转换到物体空间计算得到的特征线.7)划界线(demarcatingcurves).模型表面曲率变化最快的部位.适用于生成考古模型的线绘制结果.8)高度边缘线(reliefedges).将模型表面看作是以某个光滑曲面为基的高度场,定义为该高度场的边缘线.高度边缘线非常鲁棒,适用于处理含有噪声的模型.在现有的特征线定义中,绝大部分是与视点位置相关的,当视点与模型的相对位置发生变化时特征线的位置也会随之变化,需要重新计算.另外,大部分的特征线定义都需要计算模型每个顶点的某种几何量的二阶或更高阶导数值,计算量非常大.现有的物体空间线绘制算法重点考虑特征如何定义,没有考虑如何使用GPU加速计算,对于复杂模型绘制速度不能令人满意.1.3基于相似法的特征线绘制近年来,在线绘制的加速算法方面的研究工作较少.Sander等提出按照模型的法向建立层次结构,在绘制特征线时可以快速地将许多不包含特征线的区域剔除;但该方法只适用于轮廓线等直接依赖于模型法向的特征线定义,对其他的特征线无能为力.Hertzmann等提出一种称为Gaussmap的数据结构,将相似法向组合在一起,类似于文献,它也只适用于轮廓线的加速绘制.Markosian等提出一种随机跟踪的线绘制加速策略,首先随机确定一些三角形,并对其中每个三角形测试它是否与特征线相交;对于包含特征线片断的三角形,沿交点向相邻三角形进行跟踪,直至得到完整的特征线;该方法适用于任何一种特征线定义,但是由于其随机特性,不能保证找出所有的特征线,在视点动态变化时会因帧与帧之间的不连续性而发生视觉抖动.最新的NVIDIASDK中包含了一个使用GPU绘制三角网格模型的轮廓线的实例,该方法只适用于轮廓线的绘制,不能绘制其他的物体空间特征线.2模型表面特征函数值的计算Hertzmann等提出,三维模型的轮廓线可以看作满足n·v=0的等值线,其中,n和v分别表示模型各点的法向和视线方向.受其启发,本文提出所有的物体空间线绘制算法都归结为绘制模型表面某种函数值为0的等值线.例如,拉普拉斯线是满足Δn·v=0的等值线,其中,n和v的含义与轮廓线中的含义相同,而Δn是模型表面法向的拉普拉斯.为方便描述,本文中将这类与特征线定义相关的函数称为特征函数.基于以上观察,物体空间线绘制算法可以归纳为一个通用的算法框架,其步骤如下:Step1.根据特征线的定义计算模型每个顶点的特征函数值.Step2.计算模型表面特征函数的值为0的等值线,这可归结为一个逐三角形的计算.对每个三角形,检查3个顶点的特征函数值符号是否一致;当且仅当某个顶点的特征函数值与其他2个顶点异号时,该三角形存在一条特征线片断,即某条特征线经过该三角形.对于这样的情况,通常通过线性插值计算出特征线片断的2个端点坐标.相应地,本文提出的GPU加速的物体空间特征线绘制也通过两步法实现,如图3所示.pass1.以点为几何单元绘制模型的所有顶点,在顶点渲染器中计算每个顶点的特征函数值,并输出到一个二维纹理中.一般地,对于顶点个数为N的网格模型,使用w×h的二维纹理保存所有顶点的特征函数值,其中w=-√ΝN−−√-,h=-ΝwNw-;第i个顶点对应的纹理坐标为(x,y),y=-iwiw-,x=i-y×w.pass2.绘制模型的所有三角形,在顶点渲染器中读取顶点纹理得到各顶点的特征函数值.在几何渲染器中,对于每个三角形检查是否存在某个顶点的特征函数值与其他2个顶点的特征函数值异号.若存在,则通过线性插值计算特征线片断的2个端点的坐标,并将特征线片断输出到图形流水线中.其中,几何渲染器的输入几何单元为三角形,输出单元为线段.几何渲染器的伪代码如下:EndProcedureDrawFeatureLineΡrocedureDrawSegment(p1,p2,p3,f1,f2,f3)α1←f1f1-f2,α2←f1f1-f3,Q1←(1-α1)p1+α1p2,Q2←(1-α2)p1+α2p3OutputSegment(Q1,Q2)#输出特征线片断EndProcedureDrawSegment3加快pel轮廓的形成和成像基于图3所示的算法框架,本文实现了轮廓线和PEL2种特征线绘制算法的GPU加速.本节对这2种特征线的GPU算法进行详细介绍.3.1gpu加速绘制轮廓线的特征函数是f=n·v,其中各顶点的法向n是已知的,而视线方向v仅与顶点的三维坐标p有关,记视点位置为e,则v=e-p|e-p|.由于轮廓线的特征函数计算非常简单,因此本文在实现轮廓线的GPU绘制时并没有严格地按照算法框架分两步计算,而是把两步合二为一,通过单个步骤实现轮廓线的GPU加速绘制.如图4所示,算法以三角形为几何单元绘制模型,每个顶点传入顶点渲染器的属性值包括三维坐标p与法向n;在顶点渲染器中计算各顶点的视线方向v以及f=n·v,并将各顶点的p和f传到几何渲染器.在几何渲染器中,检查3个顶点的特征函数值是否存在异号的情况,若存在,则通过插值计算特征线片断的2个顶点坐标;像素渲染器仅需简单地输出统一的线条颜色即可.3.2采用平台的pel计算PEL是由Xie等提出的一种网格模型特征线绘制方法,从理论上讲,它相当于是采用漫反射光照明模型绘制网格模型后,再对所得光照图采用Canny边缘检测算子得到的图像边缘线.与之不同的是,PEL只在物体空间定义的特征线,其计算在物体空间完成,计算结果更加鲁棒,生成的线绘制图像更加光滑和连续.PEL定义为满足DdI=0,DdDdI<0的特征线,即其特征函数为f=DdI,其中,d=I/I,I=n·v.如图5所示,本文通过4个pass实现GPU加速的PEL绘制.其中,pass1用于计算各顶点的光亮度I=n·v;pass2用于计算各顶点的I;pass3用于计算各顶点的特征函数值Dd|Ι|=I·d.pass1～pass3相当于第3节算法框架中的pass1;而pass4则与算法框架中的pass2相同,根据之前计算的各顶点的特征函数值生成线绘制结果.3.2.1GPU加速的梯度场计算在绘制PEL时最主要的问题在于如何计算模型表面二维标量场的梯度场,或者说给定每个顶点的一个标量函数值f,如何计算出各顶点的梯度f.Xie等提出一种两步法计算各顶点的函数梯度,该方法归结为一个逐三角形的计算,并不适用于GPU加速.为此,本文提出一种逐顶点的函数梯度计算方法.设f是网格模型M上的一个标量场,p是M的任一顶点,u和v是顶点p的2个主曲率方向.记顶点p的所有相邻三角面片为Fk(k=1,…,m),并分别记Fk3个顶点的索引值为k1,k2和k3,函数值为fk1,fk2和fk3.在Fk上任取平面直角坐标系(xk,ok,yk),并将3个顶点在该坐标系下的坐标记为(xki,yki),i=1,2,3,则f在三角形Fk内的梯度其中,Ak=(xk1yk2-yk1xk2)+(xk2yk3-yk2xk3)+(xk3yk1-yk3xk1)是三角形Fk的有向面积的2倍.容易验证,该定义中的函数梯度fFk与坐标系(xk,ok,yk)的选取无关.记uk,uk为u,v在三角面片Fk上的投影,则顶点p处f的函数梯度其中wk是Fk相邻三角面片的加权系数,可取为顶点p的Voronoi图中位于三角面片Fk中的面积与总面积之比,可以在模型调入后一次性预计算得到.令Ck=wkAk(uk⋅xkuk⋅ykvk⋅xkvk⋅yk)⋅(yk2-yk3yk3-yk1yk1-yk2xk3-xk2xk1-xk3xk2-xk1)=(ak1ak2ak3bk1bk2bk3),则有按照式(1)计算梯度f(p)很容易在顶点渲染器中实现.在预处理阶段(读入模型以后),对模型中的每个顶点p计算每个相邻顶点q的权值α(q)和β(q);在计算函数梯度时(pass2,pass3),对每个顶点p将它所有相邻顶点q的索引号以及权值α(q)和β(q)作为顶点属性值传入图形流水线;在顶点渲染器中,根据各相邻顶点q的索引号计算出相应的纹理坐标,并通过读取顶点纹理获得各顶点的函数值f(q),并按照式(1)通过加权和计算出当前顶点的函数梯度.4加速的轮廓线绘制我们基于OpenGL和Cg语言实现了第3节提出的GPU加速的轮廓线绘制与PEL绘制算法.在实现中将轮廓线绘制与PEL绘制整合一起,通过在绘制PEL的pass4中加入轮廓线绘制的代码,实现了轮廓线与PEL的同时绘制.4.1评估轮廓线与gpu的绘制速度本文对一些常见模型进行了测试,分别采用GPU算法与传统CPU算法生成线绘制结果,并对绘制速度进行比较,结果如表1所示.表1中,第3,4列分别是使用CPU算法与GPU算法进行特征线绘制的速度;第5列是采用GPU加速获得的加速比,即使用GPU绘制的帧率与使用CPU绘制的帧率之比.其中,CPU算法和GPU算法的绘制速度都是在同时绘制轮廓线与PEL的情况下测得的.测试平台的硬件配置为IntelCoreDuo3.0GHzCPU,NVIDIAGTX285GPU.使用本文提出的GPU算法对所有的测试模型进行绘制,至少比使用传统CPU算法绘制速度快11倍,在最好的情况下,速度提升超过16倍(对于Buddha模型).根据近年来CPU与GPU的发展趋势来看,随着时间的推移,GPU相对CPU的性能优势会越来越明显,因而采用GPU算法的加速效果也会越来越好.另一方面,由于GPU算法与CPU算法相比并没有采用任何近似计算,因此GPU算法生成的线绘制结果与CPU算法的结果几乎没有差别,如图2所示.图6展示了更多的使用GPU算法生成的轮廓线与PEL绘制结果.4.2相邻点对点信息占用本文算法消耗的存储空间(显存)主要体现在2个方面:一是作为图形流水线输入的各顶点的属性值,二是用于保存各顶点的特征函数值或中间值的二维纹理.对于轮廓线绘制,每个顶点只需要顶点位置和法向2个基本的属性值,而这2个属性值在绝大多数情况下都是必须的;另一方面,轮廓线绘制可以在单个pass中完成,不需要额外的纹理来保存各顶点的特征函数值.因此可以认为轮廓线的GPU加速绘制不消耗额外的存储空间.对于PEL绘制,每个顶点需要传入较多的属性值.除了位置与法向外,还需要传入所有相邻顶点的索引值以及2个计算梯度值的加权系数,这样,对每个相邻顶点需要保存3个浮点数.在当前的图形流水线中,要求每个顶点具有相同大小的属性数据.本文在实现中对每个顶点都保存12个相邻顶点的索引号和加权系数(包括自身),对于相邻顶点数不足12的顶点,将不足的部分记顶点索引号为-1.在本文测试的所有模型中,没有出现相邻顶点数达到