一种高效并行矢量数据可视化方法

摘要

本发明公开了一种高效并行矢量数据可视化方法，该方法可快速、高质量地绘制复杂矢量图形。本发明提出了一种在矢量图形轮廓线上求值并绘制的扫描线算法，算法并行在矢量图形轮廓线上进行光栅化。算法首先将图形轮廓线光栅化为对应输出图像上像素的片段。在每个轮廓线片段上，解析计算得到颜色值，或近似使用采样算法采样得到颜色值。图像轮廓的光栅化可以高效并行完成。解析计算、32位采样可得到高质量的结果。本发明在扫描线方向上，采用并行前缀和算法计算得到每个像素的覆盖信息，并生成图像的填充区域。最后将矢量图形的轮廓片段和填充区域绘制到输出图像上。本发明完全使用并行众核运算设备实现，利用硬件加速实现了实时高质量矢量图形绘制。

说明书

技术领域

本发明涉及图形绘制领域，尤其涉及一种高效并行矢量数据可视化方法。

背景技术

本发明相关的研究背景简述如下：

二维矢量图形绘制是计算机图形学中的一个重要领域。矢量图形由轮廓和 填充区域组成。矢量图形的轮廓是一组首位相接的曲线，使用数学公式解析表 达，通常由贝塞尔曲线或其他有理样条曲线分段表示。矢量图形的填充区域使 用非零环绕数规则、奇偶判别规则确定。矢量图形的颜色可以选择单色、线性 渐变色、辐射渐变色、纹理方式表示。

一、矢量图形绘制：

Loop等人提出了把矢量图形分割成三角形，在可编程着色器里判断像素是 否落在矢量图形内部的方法(LOOP,C.,ANDBLINN,J.2005.Resolution independentcurverenderingusingprogrammablegraphicshardware.ACM Trans.Graph.24,3(July),1000–1009.)。微软的Direct2D使用梯形划 分矢量图形进行绘制，在边界上计算覆盖值(KERR,K.2009.Introducing Direct2D.MSDNMagzine3,4.)。Kokojima等人的方法生成矢量图形的三角形 覆盖，并使用模板缓存进行绘制(KOKOJIMA,Y.,SUGITA,K.,SAITO,T.,AND TAKEMOTO,T.2006.Resolutionindependentrenderingofdeformablevector objectsusinggraphicshardware.InACMSIGGRAPH2006Sketches,ACM,New York,NY,USA,SIGGRAPH’06.)。NVPR(NV_path_rendering)使用基于模板 缓存绘制的方法(KILGARD,M.J.,ANDBOLZ,J.2012.GPU-acceleratedpath rendering.ACMTrans.Graph.31,6(Nov.),172:1–172:10.)，该方法在 GPU上实现了实时绘制。

Vectortexture类方法使用预处理步骤构造出加速数据结构，利用加速数据 结构，在绘制过程中快速判断点与图形的相对位置并获得相关的颜色等信息 (NEHAB,D.,ANDHOPPE,H.2008.Random-accessrenderingofgeneral vectorgraphics.ACMTrans.Graph.27,5(Dec.),135:1–135:10.；；WANG, L.,ZHOU,K.,YU,Y.,ANDGUO,B.2010.Vectorsolidtextures.ACMTrans. Graph.29,4(July),86:1–86:8.等)。这类算法的预处理过程通常要在CPU 上使用较长时间完成。Ganacim等人提出的ShortcutTree数据结构可以使用GPU 并行构造(GANACIM,F.,LIMA,R.S.,DEFIGUEIREDO,L.H.,ANDNEHAB,D. 2014.Massively-parallelvectorgraphics.ACMTrans.Graph.33,6(Nov.), 229:1–229:14.)，然而在绘制大规模复杂动态矢量图形时，数据结构生成的开 销仍大于绘制过程的开销。

二、反走样：

反走样算法用于消除绘制过程中在图像边界上产生的失真。NVPR使用OpenGL 的多重采样功能进行反走样(SEGAL,M.,ANDAKELEY,K.,2003.TheOpenGL graphicssystem:Aspecification. http://www.opengl.org/documentation/specs/version1.5/glspec15.pdf.)。 多重采样需要在同一像素多次计算颜色值，以获得更好的反走样效果，从而导 致计算量增加和绘制速度降低。Manson等人提出了解析计算积分的方法反走样 (MANSON,J.,ANDSCHAEFER,S.2013.Analyticrasterizationofcurves withpolynomialfilters.ComputerGraphicsForum(Proceedingsof Eurographics)32,2,499–507.)，该方法从理论上得到了矢量图形在像素上 覆盖面积的解析表示，但绘制速度较慢。

发明内容

本发明的目的在于针对现有技术的不足，提供一种高效并行矢量数据可视 化方法。

本发明的目的是通过以下技术方案来实现的：一种高效并行矢量数据可视 化方法。该方法使用分段贝塞尔曲线以及有理样条曲线表示矢量图形，使用带 透明度的单色、线性渐变色、辐射渐变色表示图形的轮廓颜色和填充颜色。

该方法使用并行扫描线算法，使用图形处理器并行加速完成图形绘制。该 方法首先使用轮廓曲线表示矢量图形。绘制过程首先在图形的每段轮廓线上进 行。每段轮廓线被并行裁剪成若干片段，每个片段对应绘制结果中的一个像素。 在每个片段上，根据轮廓线片段的公式，得到之后用于计算颜色的中间结果。 然后，根据这些中间结果，在每条横向扫描线上，计算得到矢量图形轮廓上的 颜色，以及矢量图形内部的填充区域。最后，将轮廓线以及填充区域共同绘制， 得到输出图像上每个像素的颜色。该方法能在不同使用条件下，分别支持非零、 奇偶填充模式。支持单色、线性渐变色、辐射渐变色等填充模式。具体可采用 两种方案来实现：

方案一：一种高效并行矢量数据可视化方法，包括以下步骤：

(1)对矢量图形轮廓线并行裁剪处理，将每条轮廓线沿像素边界裁剪成像 素内的轮廓线片段；

(2)根据反走样算法并行处理每个轮廓片段，在每个片段上得到用于计算 覆盖值的中间结果；所述反走样算法为解析法，具体如下：

基于以下公式计算每个像素上的覆盖值：

$F(x,y)=\int {\int }_{u,v\in M}h\left(u-x,v-x\right)dudv---\left(1\right)$

$=F_0(x,y)+\underset{i=0}{\overset{x-1}{\Sigma }}{F}_1(i,y)---\left(3\right)$

其中：

$H(u,v)={\int }_0^{u}h(s,v)ds$

$F_0(x,y)={\int }_0^{1}H\left(u\left(t\right)-x,v\left(t\right)-y\right)v^{\prime }\left(t\right)dt---\left(4\right)$

$F_1(x,y)={\int }_0^{1}H\left(u\left(t\right)-\left(x+1\right),v\left(t\right)-y\right)v^{\prime }\left(t\right)dt---\left(5\right)$

F(x,y)表示位于坐标(x,y)处像素的轮廓在该像素内的覆盖值；u、v是矢量 图形上的坐标；u(t)、v(t)分别是像素(x,y)内轮廓线公式的x、y分量；M表示 矢量图形的内部区域；表示矢量图形的边界；函数h在1x1大小的单位像素 内有常数值1；函数H由函数h横向积分获得；

并行处理每个轮廓线片段，将轮廓线片段的表达式代入公式(4)、公式(5)， 计算每个片段对应的中间结果F₀(x,y)和F₁(x,y)；

(3)并行对所有轮廓线片段对应的值按照其像素位置进行排序，在每个矢 量图形内将片段按照先行后列的顺序排列；

(4)在每个矢量图形内的每行轮廓线上，并行完成片段在像素上覆盖值的 计算，具体为，并行计算公式(3)中的求和项，并记为：

$A(x,y)=\underset{i=0}{\overset{x-1}{\Sigma }}{F}_1(i,y)$

并行在每个像素位置上将A(x,y)和F₀(i,y)相加，得到轮廓在像素上的覆盖 值F(x,y)；

(5)生成用于绘制矢量图形填充颜色的区域：若相邻两个位置的轮廓线片 段位于同一行并且属于同一个矢量图形，使用以下方法判断两个片段之间的区 域是否属于图形内部：右侧片段处的A(x,y)值大于0；

并行处理所有相邻的轮廓线片段，根据以上规则判断两片段之间的区域是 否属于矢量图形内部；记录属于矢量图形内部的填充区域；

(6)绘制片段及填充区域：使用图元表示所有轮廓片段和填充区域；将轮 廓线片段的覆盖值用于反走样，绘制所有图元。

进一步地，所述步骤1具体包括以下子步骤：

(1.1)输入的矢量图形的轮廓线采用参数公式P＝C(t)表示；参数t是[0,1] 之间的实数，P是轮廓线上的点；并行处理每段轮廓线，求得其与像素边界对齐 的最小包围盒，得到在x轴、y轴上覆盖轮廓线的范围[x_l,x_h]、[y_l,y_h]，x_l、x_h、 y_l、y_h分别表示x轴下界、x轴上界、y轴下界、y轴上界；

(1.2)分别在x、y轴方向上，包围盒范围内，每隔1个像素单位长度， 对像素边界和轮廓线求交，得到交点处轮廓线参数t；按照升序把所有交点参数 t记录到数组T＝[t_i]中，其中t_i代表第i个交点处的参数；至此，数组T中每两 个相邻参数之间对应一个轮廓线片段；

(1.3)并行处理每对相邻的参数，将轮廓线公式裁剪为每个像素内的片段， 并将裁剪后的片段记录到数组S中；属于同一矢量图形的片段在数组S中连续 存储；裁剪之后，移除位于图像上边界、下边界外侧的片段。

进一步地，所述步骤3具体为：使用并行分段排序算法对所有值进行排序， 属于同一矢量图形的所有片段为一个分段，在每个分段上，以轮廓线片段所在 像素的y坐标为第一关键字，以轮廓线片段所在像素的x坐标为第二关键字； 排序后，每个矢量图形内的片段值按照先行后列的顺序排列。

方案二：一种高效并行矢量数据可视化方法，包括以下步骤：

(1)对矢量图形轮廓线并行裁剪处理，将每条轮廓线沿像素边界裁剪成像 素内的轮廓线片段；

(2)根据反走样算法并行处理每个轮廓片段，在每个片段上得到用于计算 覆盖值的中间结果；所述反走样算法为多重采样法，具体如下：

在每个像素内使用若干个采样点，测试每个采样点是否落在矢量图形内部； 使用整数掩码数表示像素内的采样结果；整数中一个二进制位对应一个采样点， 二进制位为1表示采样点落在图形内部，0表示采样点落在图形外部；每个像素 上的掩码使用以下公式计算得到：

$F(x,y)=F_0(x,y)\oplus \underset{i=0}{\overset{x-1}{\oplus }}{F}_1(i,y)---\left(6\right)$

其中F(x,y)表示位于(x,y)位置处像素的掩码；F₀(x,y)表示(x,y)处的像素 里，落在轮廓曲线右侧的采样点；F₁(x,y)表示(x+1,y)处的像素里，落在轮廓 曲线右侧的采样点；

使用预计算生成掩码表，在绘制过程中使用查表的方式得到轮廓片段的掩 码F₀和F₁；

(3)并行对所有轮廓线片段对应的值按照其像素位置进行排序，在每个矢 量图形内将片段按照先行后列的顺序排列；

(4)在每个矢量图形内的每行轮廓线上，并行完成片段在像素上覆盖值的 计算，具体为：

并行计算公式(6)中所有F₁的异或，并记为：

$A(x,y)=\underset{i=0}{\overset{x-1}{\oplus }}{F}_1(i,y)$

并行在每个像素位置上将A(x,y)和F₀(i,y)计算异或，得到轮廓在像素上的 采样点掩码F(x,y)；

(5)生成用于绘制矢量图形填充颜色的区域：若相邻两个位置的轮廓线片 段位于同一行并且属于同一个矢量图形，使用以下方法判断两个片段之间的区 域是否属于图形内部：右侧片段处的A(x,y)非0；

并行处理所有相邻的轮廓线片段，根据以上规则判断两片段之间的区域是 否属于矢量图形内部；记录属于矢量图形内部的填充区域；

(6)绘制片段及填充区域：使用图元表示所有轮廓片段和填充区域；使用 图形绘制流水线的多重采样功能，将计算得到的采样掩码作为绘制使用的采样 掩码，绘制所有图元。

进一步地，所述步骤1具体包括以下子步骤：

(1.1)输入的矢量图形的轮廓线采用参数公式P＝C(t)表示；参数t是[0,1] 之间的实数，P是轮廓线上的点；并行处理每段轮廓线，求得其与像素边界对齐 的最小包围盒，得到在x轴、y轴上覆盖轮廓线的范围[x_l,x_h]、[y_l,y_h]，x_l、x_h、 y_l、y_h分别表示x轴下界、x轴上界、y轴下界、y轴上界；

(1.2)分别在x、y轴方向上，包围盒范围内，每隔1个像素单位长度， 对像素边界和轮廓线求交，得到交点处轮廓线参数t；按照升序把所有交点参数 t记录到数组T＝[t_i]中，其中t_i代表第i个交点处的参数；至此，数组T中每两 个相邻参数之间对应一个轮廓线片段；

(1.3)并行处理每对相邻的参数，将轮廓线公式裁剪为每个像素内的片段， 并将裁剪后的片段记录到数组S中；属于同一矢量图形的片段在数组S中连续 存储；裁剪之后，移除位于图像上边界、下边界外侧的片段。

进一步地，所述步骤3具体为：使用并行分段排序算法对所有值进行排序， 属于同一矢量图形的所有片段为一个分段，在每个分段上，以轮廓线片段所在 像素的y坐标为第一关键字，以轮廓线片段所在像素的x坐标为第二关键字； 排序后，每个矢量图形内的片段值按照先行后列的顺序排列。

本发明的有益效果是：

(1)能够绘制通用标准矢量图形。本发明支持通用的矢量图形表示方式， 支持一次、二次、三次贝塞尔曲线、二次有理样条曲线表示的矢量图形边界； 支持单色、线性渐变、辐射渐变填充；支持带透明度的填充。

(2)能够快速绘制复杂矢量图形。本发明提出的方案给出了简单、通用的 并行运算步骤，可以在各类众核系统、图形处理器设备上使用。

(3)能够绘制高质量反走样的矢量图形。本发明支持解析计算和多重采样 两种反走样方法，可以达到高质量的反走样效果。

附图说明

图1：(a)图展示了将一条轮廓线沿像素边界裁剪为轮廓线片段的过程。短 点划线为纵向像素边界，长点划线为横向像素边界。正方形标志为轮廓线与横 向像素边界的交点，三角型标志位轮廓线与纵向像素边界交点。沿交点裁剪后 的轮廓线生成(b)中所示的轮廓线片段，片段由黑色实心点分割，每个深色方 格对应轮廓线所在的像素。

图2：图片展示了采样位掩码中F₀和F₁的计算。粗线为像素边界。短点线表 示预计算表的顶点划分。深色部分为矢量图形内部。左侧像素为当前处理的像 素。圆形点表示未落在矢量图形内部的采样点；左侧像素内方形点表示F0，右 侧像素内方形点和三角形点表示F₁；三角形点表示轮廓线近似导致的采样误差。

图3：本发明实例使用32位多重采样抗锯齿绘制的汽车矢量图。图像在 1024x682分辨率下绘制。该矢量图包含420个图形，1.2万条边界线。

图4：本发明实例使用解析法抗锯齿绘制的巴黎地图矢量图。图像在 1096x1060下绘制，该矢量图包含50690个矢量图形，165万条边界。

具体实施方式

下面结合附图和具体实施例对本发明作进一下详细说明。

矢量图形绘制的技术难点在于快速判断像素是否在矢量图形内部，以及绘制 结果反走样。本发明提出了一种高效并行的矢量图形绘制方法。本方法首先将 矢量图形的轮廓线沿像素边界裁剪成像素大小的轮廓线片段，之后以轮廓线片 段为单位并行处理。本发明使用解析、采样位掩码两种反走样方法计算矢量图 形在每个像素上的覆盖。

本发明是一种高效并行矢量数据可视化方法，包括以下步骤：

(1)并行轮廓线裁剪，具体包括以下子步骤：

(1.1)输入的矢量图形的轮廓线采用参数公式P＝C(t)表示。参数t是[0,1] 之间的实数，P是轮廓线上的点。并行处理每段轮廓线，求得其与像素边界对齐 的最小包围盒，得到在x轴、y轴上覆盖轮廓线的范围[x_l,x_h]、[y_l,y_h]。x_l、x_h、 y_l、y_h分别表示x轴下界、x轴上界、y轴下界、y轴上界。

(1.2)分别在x、y轴方向上，包围盒范围内，每隔1个像素单位长度， 对像素边界和轮廓线求交，得到交点处轮廓线参数t。按照升序把所有交点参数 t记录到数组T＝[t_i]中，其中t_i代表第i个交点处的参数。至此，数组T中每两 个相邻参数之间对应一个轮廓线片段(参见附图1)。

(1.3)并行处理每对相邻的参数，将轮廓线公式裁剪为每个像素内的片段， 并将裁剪后的片段记录到数组S中。属于同一矢量图形的片段在数组S中连续 存储。裁剪之后，移除位于图像上边界、下边界外侧的片段。

(2)根据反走样算法并行处理每个轮廓片段，在每个片段上得到用于计算 覆盖值的中间结果。本发明支持两种不同的反走样算法，具体如下：

(2.1)解析法：

解析法基于以下公式计算每个像素上的覆盖值：

$F(x,y)=\int {\int }_{u,v\in M}h\left(u-x,v-x\right)dudv---\left(1\right)$

$=F_0(x,y)+\underset{i=0}{\overset{x-1}{\Sigma }}{F}_1(i,y)---\left(3\right)$

其中：

$H(u,v)={\int }_0^{u}h(s,v)ds$

$F_0(x,y)={\int }_0^{1}H\left(u\left(t\right)-x,v\left(t\right)-y\right)v^{\prime }\left(t\right)dt---\left(4\right)$

$F_1(x,y)={\int }_0^{1}H\left(u\left(t\right)-\left(x+1\right),v\left(t\right)-y\right)v^{\prime }\left(t\right)dt---\left(5\right)$

公式最后求得F(x,y)，表示位于坐标(x,y)处像素的轮廓在该像素内的覆盖 值。u、v是矢量图形上的坐标；u(t)、v(t)分别是像素(x,y)内轮廓线公式的x、 y分量；M表示矢量图形的内部区域；表示矢量图形的边界；函数h在1x1大 小的单位像素内有常数值1；函数H由函数h横向积分获得。公式3由公式2改 写得到，可以具体写成公式(4)和公式(5)的形式。

该步骤并行处理每个轮廓线片段，将轮廓线片段的表达式代入公式(4)、公 式(5)，计算每个片段上对应公式(3)中用到的中间结果F₀(x,y)和F₁(x,y)，并 将这两个值存储在数组F₀和数组F₁中。

(2.2)多重采样法：

多重采样法，在每个像素内使用8、16或32个采样点，测试每个采样点是 否落在矢量图形内部。使用整数掩码数表示像素内的采样结果。整数中一个二 进制位对应一个采样点，二进制位为1表示采样点落在图形内部，0表示采样点 落在图形外部。每个像素上的掩码使用以下公式计算得到：

$F(x,y)=F_0(x,y)\oplus \underset{i=0}{\overset{x-1}{\oplus }}{F}_1(i,y)---\left(6\right)$

其中F(x,y)表示位于(x,y)位置处像素的掩码。F₀(x,y)表示(x,y)处的像素 里，落在轮廓曲线右侧的采样点；F₁(x,y)表示(x+1,y)处的像素里，落在轮廓 曲线右侧的采样点(参见图2)。

为了在绘制过程中加速，使用预计算生成掩码表，在绘制过程中使用查表 的方式得到轮廓片段的掩码F₀和F₁。

预计算中，把每个像素划分成n*n的网格。从每个网格点出发，取k条延 伸到像素边界的线段，线段与x轴正方向的顺时针倾角在360度上均匀分布。 对于每条线段，计算该线段对应的F₀和F₁,并以格点位置和倾角作为索引，记录 在掩码表中。n和k的值可根据具体实现，均取非零正整数。

绘制过程中，并行处理每条轮廓线片段，对于曲线轮廓使用直线段近似表 示，根据线段的位置和倾角，查找预计算的掩码表，快速得到F₀和F₁的值。将这 两个值记录在数组F₀和数组F₁中。

(3)并行轮廓线片段排序：并行生成的轮廓线片段数组F₀和数组F₁中，属 于同一个矢量图形的片段上的值相邻排列；同一矢量图形中，属于同一条轮廓 线片段上的值相邻排列。本发明使用并行分段排序算法对所有值进行排序，属 于同一矢量图形的所有片段为一个分段，在每个分段上，以轮廓线片段所在像 素的y坐标为第一关键字，以轮廓线片段所在像素的x坐标为第二关键字。排 序后，每个矢量图形内的片段值按照先行后列的顺序排列。

(4)在每个矢量图形内的每行轮廓线上，使用并行前缀和算法，完成片段 在像素上覆盖值的计算，对于解析法和多重采样法分别使用以下步骤：

(4.1)解析法：

使用并行前缀和算法，计算公式(3)中的求和项，并记为：

$A(x,y)=\underset{i=0}{\overset{x-1}{\Sigma }}{F}_1(i,y)$

之后，并行在每个像素位置上将A(x,y)和F₀(i,y)相加，得到轮廓在像素上的 覆盖值F(x,y)。将A记录在数组A中，用于下一步计算。

(4.2)多重采样法：

使用并行前缀和算法，计算公式(6)中所有F₁的异或，并记为：

$A(x,y)=\underset{i=0}{\overset{x-1}{\oplus }}{F}_1(i,y)$

之后，并行在每个像素位置上将A(x,y)和F₀(i,y)计算异或，得到轮廓在像素 上的采样点掩码F(x,y)。将A记录在数组A中，用于下一步计算。

(5)生成用于绘制矢量图形填充颜色的区域：在数组A中，若相邻两个值 对应的片段位于同一行并且属于同一个矢量图形，使用以下方法判断两个片段 之间的区域是否属于图形内部：

(5.1)解析法：右侧片段处的A(x,y)值大于0。

(5.2)多重采样法：右侧片段处的A(x,y)非0。

并行处理所有相邻的轮廓线片段，根据以上规则判断两片段之间的区域是 否属于矢量图形内部。若区域属于矢量图形内部，则记录区域的y坐标、区域 在x方向上的起始和结束坐标、该矢量图形的填充颜色或填充方式。

(6)绘制片段及填充区域：使用矩形图元表示所有轮廓片段和填充区域。 为填充区域生成高为1、宽度与填充区域宽度相同的矩形图元，为轮廓线片段生 成宽、高均为1的图元。图元包含原轮廓线片段或填充区域的填充信息。对于 两种不同反走样方法，使用不同的方法生成轮廓片段对应图元中的值：

(6.1)解析法：将轮廓线片段的覆盖值作为alpha(颜色混合)值，乘以 边界本身填充颜色的alpha值，作为生成的矩形图元的alpha值。使用图形绘 制流水线的alpha混合功能，绘制所有图元。

(6.2)多重采样法：使用图形绘制流水线的多重采样功能，将计算得到的 采样掩码作为绘制使用的采样掩码，绘制所有图元。

至此，本发明的矢量图形绘制流程结束。

实施实例

发明人在NVIDIAGTX980图形处理器上实现了本发明的实施实例。本实施 实例能够在并行图形处理器上高效、高质量绘制复杂矢量图形。本实例绘制复 杂矢量图形，每秒绘制帧数能达到30帧以上。

表1是本实施实例绘制不同矢量图形的耗时、内存统计。

附图3、4是上表中汽车和巴黎地图-30的绘制结果但由于排版的原因图片 可能会有裁剪。

从实例可以看出，本发明能够实现快速、高质量绘制矢量图形的效果。