METHOD, SYSTEM AND DEVICE FOR PROCESSING VECTOR GRAPHICS IN COMPUTER IMAGE PROCESSING

计算机图像处理中矢量化图形的处理方法及系统和装置

技术领域

本发明涉及计算机图像处理， 特别涉及有序活动边表的三角化技术和图 像压缩技术。

背景技术

计算机图像处理领域中的三角化算法是把一系列复杂多变的多边形切 分成一组三角形， 使得三角化的形状勾称和计算速度快。 由于在图形处理器 内部实现了任意三角形的光栅化， 因此对于速度的要求更为突出。 现有三角化技术主要如下：

Delaunay三角剖分法， 其应用最为广泛。 从 Delaunay三角网的性质上 可以发现这些性质： Delaunay三角网是唯一的， 三角网的外边界构成了点集 P的凸多边形 "外壳" ， 没有任何点在三角形的外接圆内部。 如果一个三角 网满足上述条件， 则称为 Delaunay三角网。

如果将三角网中的每个三角形的最小角进行升序排列， 则 Delaunay三 角网的排列得到的数值最大， 从这个意义上讲， Delaunay三角网是 "最接近 于规则化" 的三角网。 但是， 本发明的发明人发现， 若从时间复杂度上讲， Delaunay算法得到的三角形数目较多形状较小， 计算量大、 复杂度高， 处理 速度比较慢。

此外， 依在计算机中的存储和表示的区别， 图形被分为矢量图和位图两种。 矢量图， 在计算机里存储的是绘图的数学算法； 位图， 在计算机里存储的是像 素的位置信息和颜色信息以及灰度信息。

目前， 计算机图形处理器在绘制矢量图时， 一般是由位图仿图绘制出来。 仿制的过程中， 首先提取位图的轮廓， 然后将图的轮廓进行三角剖分， 剖分为 一组三角形的组合。 如果图轮廓本身是多边形， 则直接对该多边形进行三角剖 分， 如果图轮廓有曲边， 以一个圆为例， 则首先将这个圆转换成一个近似的多 边形， 再对这个多边形进行三角剖分。 若要使转换后的多边形越接近这个圆， 则要求多边形的边的数量越多， 多边形的边无限多时， 则该多边形无限逼近这 个圆。 对于复杂的图轮廓， 在三角剖分后， 将产生非常庞大的三角形集合。

在对多边形进行三角剖分时， 有很多不同的方法， 目前计算机中常用的一 种方法是利用一组平行于 X轴的扫描线对多边形进行剖分，该组扫描线刚好覆盖 了多边形的所有顶点， 该方法分得的图元有： 梯形， 正三角形和倒三角形三种， 如图 10所示， 其中， 方形可以作为特殊的梯形。 梯形在后续处理中还将进一步 分成两个三角形。

在对多边形进行三角剖分后要进行编码存储。 目前， 一般采用差分编码对 三角剖分后的图元进行编码。 以一个梯形为例， 有一种编码存储方法是， 存储 第一个顶点坐标值为 （xl、 yl ), 然后存储第二个点的坐标值与第一个点的坐标 值的差值〔（x2-xl )、 （y2-yl )〕， 与此类似， 存储的第三个点的信息为〔（x3-x2 )、 ( y3-y2 )〕， 存储的第四个点的信息为 〔（x4-x3 )、 ( y4-y3 ) l 当图形轮廓复杂， 图元数量非常庞大时， 如何做到保证编码精度又尽量 减少编码后的数据量， 以在存储编码数据时减少占用编码设备宝贵的内存空 间， 成为了研究的一个热点。

发明内容

本发明的目的在于提供一种计算机图像处理中矢量化图形的处理方法 及系统和装置， 减少了不必要的三角形切分， 所组成的三角形数目较少， 形 状较大， 大大减少了计算机图形处理部件的计算量， 后续在三角形基础上的 图形处理效率较高。 并且可以提高数据的压缩率， 节省压缩计算量。 为解决上述技术问题， 本发明的实施方式公开了一种计算机图像处理中 多边形的三角化方法， 包括以下步骤： 对多边形的各个顶点根据指定坐标轴的坐标值大小进行排序； 根据经排序的各顶点建立活动边表； 依次发出穿过经排序的各顶点且垂直于指定坐标轴的扫描线， 对于每一 条穿过当前顶点的当前扫描线： 根据活动边表得到对应的活动边， 对当前扫描线穿过的活动边进行计 数， 根据计数确定各活动边之间区域的有效性， 仅在当前扫描线之上且与当 前顶点连通又还未被三角化的有效区域中组建三角形， 供计算机的图形处理 器渲染图像使用。 本发明的实施方式还公开了一种计算机图像处理中多边形的三角化系 统， 包括以下模块： 排序模块， 用于对多边形的各个顶点根据指定坐标轴的坐标值大小进行 排序；

建表模块， 用于根据经排序模块排序的各顶点建立活动边表； 扫描模块， 用于依次发出穿过经排序模块排序的各顶点且垂直于指定坐 标轴的扫描线； 获取模块， 用于对于扫描模块发出的每一条穿过当前顶点的当前扫描 线， 根据建表模块建立的活动边表得到对应的活动边； 计数模块， 用于对于扫描模块发出的每一条穿过当前顶点的当前扫描 线， 对当前扫描线穿过的活动边进行计数； 确定模块， 用于根据计数模块得到的计数， 确定获取模块获取的各活动 边之间区域的有效性； 组建模块， 用于仅在当前扫描线之上且与当前顶点连通又还未被三角化 的有效区域中组建三角形， 供计算机的图形处理器渲染图像使用。 本发明实施方式与现有技术相比， 主要区别及其效果在于：

因为仅在与顶点连通的当前扫描线之上的有效区域组建三角形， 减少了 不必要的三角形切分， 所组成的三角形数目较少， 形状较大， 大大减少了计 算机图形处理部件的计算量， 且后续在三角形基础上的图形处理效率较高。 进一步地， 由顶点的下边表的有序及顶点的有序保证了活动边的有序， 因此在每次发扫描线时不需要对所有活动边求交， 对交点排序， 所以计算量 大大减少；

进一步地， 在有序活动边表的三角化方法中， 使用奇偶填充规则， 通过 只对在当前扫描线之上的当前顶点的最近左边和最近右边之间的有效区域， 组建三角形， 从而进一减少了计算量； 进一步地， 在有序活动边表的三角化方法中， 使用非零填充规则， 通过 只对在当前扫描线之上的当前顶点的最远左边和最远右边之间的有效区域， 组建三角形， 从而进一减少了计算量； 进一步地， 在对多边形的顶点排序时， 由于对顶点索引表进行的快速排 序只交换指针而不交换数据， 使得内存数据的在内存中的位置挪移最少， 减 少了系统负载， 提高了图形处理效率。 本发明实施方式中还提供了一种计算机图像处理中对矢量化图形进行数据 压缩的方法， 包括：

采用扫描线将待处理的矢量图形切分为若干图元；

分别确定每一条扫描线切分获得的图元， 记录每一条扫描线的纵坐标， 并 确认任意一图元在其对应的扫描线上的顶点， 与该扫描线具有相同纵坐标； 分别根据每一个图元在其对应的扫描线上的顶点， 确定相应图元的基准 点； 分别基于每一个图元的基准点的坐标， 以差分编码形式记录相应图元各顶 点的坐标。

本发明实施方式中还提供了一种计算机图像处理中对矢量化图形进行数据 压缩的装置， 包括：

切分单元， 用于采用扫描线将待处理的矢量图形切分为若干图元； 第一处理单元， 用于分别确定每一条扫描线切分获得的图元， 记录每一条 扫描线的纵坐标， 并确认任意一图元在其对应的扫描线上的顶点， 与该扫描线 具有相同纵坐标；

第二处理单元， 用于分别根据每一个图元在其对应的扫描线上的顶点， 确 定相应图元的基准点， 并分别基于每一个图元的基准点的坐标， 以差分编码形 式记录相应图元各顶点的坐标。

本发明实施例中， 根据有序活动边表三角化方法所切分的三角形的特点， 在压缩算法上采用了改进的差分压缩算法， 以扫描线为单位对数据进行压缩， 即针对每一条扫描线切分得到的所有图元在相应扫描线上的顶点的纵坐标均相 同的特点， 首先存储了每条扫描线切分得到的图元的数目和每条扫描线的纵坐 标， 然后以每个图元在相应扫描线上的某一顶点为基准点， 根据每一个图元的 基准点的坐标， 依次存储相应图元各顶点的坐标值和基准点坐标值的差值， 较 佳的， 所有坐标值均以定点数 11.5的格式存储， 这样， 便优化地完成了数据的压 缩操作， 节省了针对同样的图形多次做压缩所带来的计算性能上的开销， 同时 提高了数据的压缩率， 在提高编码效率的同时， 减少了对计算机系统的存储空 间的占用。 特别是在图元数量非常庞大的时候， 这种方法可比现有技术节省 20%-30%的内存空间， 也更适合用于存储空间比较有限的嵌入式计算机系统 中。

附图说明

图 1是本发明第一实施方式中一种计算机图像处理中多边形的三角化方 法的流程示意图； 图 2是本发明第二实施方式中一种计算机图像处理中多边形的三角化方 法的流程示意图； 图 3是本发明第二实施方式中一种计算机图像处理中多边形的三角化方 法的流程示意图； 图 4是本发明第二实施方式中一种计算机图像处理中多边形的三角化方 法的一种多边形示意图； 图 5 ( a )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形示意图； 图 5 ( b )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形效果示意图； 图 5 ( c )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形效果示意图； 图 6 ( a )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形示意图； 图 6 ( b )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形效果示意图； 图 6 ( c )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形效果示意图；

图 7是本发明第三实施方式中一种计算机图像处理中多边形的三角化系 统的结构示意图； 图 8是本发明第四实施方式中一种计算机图像处理中多边形的三角化系 统的结构示意图； 图 9是本发明第四实施方式中一种计算机图像处理中多边形的三角化系 统的结构示意图。

图 10为现有技术下采用扫描线分割多边形的示意图；

图 11A为本发明实施例中图形压缩装置功能结构示意图；

图 11B为本发明实施例中矢量图形三角化示意图；

图 12为本发明实施例中对矢量化图形进行三角化数据压缩流程图。

具体实施方式

在以下的叙述中， 为了使读者更好地理解本申请而提出了许多技术细 节。 但是， 本领域的普通技术人员可以理解， 即使没有这些技术细节和基于 以下各实施方式的种种变化和修改， 也可以实现本申请各权利要求所要求保 护的技术方案。 为使本发明的目的、 技术方案和优点更加清楚， 下面将结合附图对本发 明的实施方式作进一步地详细描述。 本发明第一实施方式涉及一种计算机图像处理中多边形的三角化方法。 图 1是该计算机图像处理中多边形的三角化方法的流程示意图。 该计算机图 像处理中多边形的三角化方法包括以下步骤： 在步骤 101 中， 对多边形的各个顶点根据指定坐标轴的坐标值大小进行 排序。

此后进入步骤 102 , 根据经排序的各顶点建立活动边表。 多边形顶点位置及其先后连接关系按序排列生成有序顶点集合， 用于表 示该多边形， 通过对其进行遍历即可生成该多边形的活动边表。 活动边表的 建立方法包括但不限于矢量顶点方式按照坐标方向排序生成活动边表， 也可 以多边形顶点对角连线的方式生成活动边表。 此后进入步骤 103, 依次发出穿过经排序的某一顶点且垂直于指定坐标 轴的扫描线。 此后进入步骤 104, 对于穿过当前顶点的当前扫描线， 根据活动边表得 到对应的活动边。 此后进入步骤 105, 根据所得到的活动边， 对当前扫描线穿过的活动边 进行计数。

此后进入步骤 106, 根据计数确定各活动边之间区域的有效性。 在本发明的实施方式中， 有效区域为可以进行三角化的区域。

此后进入步骤 107, 在当前扫描线之上且与当前顶点连通又还未被三角 化的有效区域中组建三角形， 供计算机的图形处理器渲染图像使用。

仅在与顶点连通的当前扫描线之上的有效区域组建三角形， 减少了不必 要的三角形切分， 所组成的三角形数目较少， 形状较大， 大大减少了计算机 图形处理部件的计算量， 后续在三角形基础上的图形处理效率较高。 此后进入步骤 108, 判断当前顶点是否为有序活动边表中的最后一个顶 点。 若是， 则结束本流程； 否则返回步骤 103, 依次发出穿过经排序的当前 顶点的下一顶点且垂直于指定坐标轴的扫描线。 本发明第二实施方式涉及一种计算机图像处理中多边形的三角化方法。 第二实施方式在第一实施方式的基础上进行了改进， 主要改进之处在于： 有 序活动边表的三角化通过表中活动边和顶点的有序，每次发送扫描线时,无需 对所有活动边求交以及直接对交点排序， 大大减少了计算量。 同时， 使用相 应的法则， 确定三角化的有效区域， 进一步减少了计算量， 提高了图像处理 效率。 图 2是该计算机图像处理中多边形的三角化方法的流程示意图。 如图 2 所示的该计算机图像处理中多边形的三角化方法， 具体地说： 在步骤 201 中， 根据指定坐标轴的坐标值大小和使用快速排序法， 对多 边形的各个顶点进行排序。 此后进入步骤 202 , 根据经排序的各顶点并按照其所对应的活动边的斜 率大小排序建立活动边表。 相应地， 在活动边表中， 每个顶点所对应的活动边包括但不限于按斜率 大小排序， 若按照斜率进行活动边排序， 则其斜率获取可以通过每条活动边 的一顶点与另一顶点之间的横坐标增量 DX与纵坐标增量 DY的比值 DX/DY 实现， 斜率越小表示越 "右边" ， 斜率越大表示越 "左边" ， 一个顶点发了 扫描线， 并生成完三角形后， 会把其所有已排序的下边， 加入到现有的有序 活动边表， 构成一个新的有序活动边表， 并且已经是排好序的。 这样发扫描 线， 找最近、 最远的边时， 就节省了系统计算工作量， 减少了系统负载， 提 高系统工作效率。 此后进入步骤 203, 依次发出穿过经排序的当前顶点的下一顶点且垂直 于指定坐标轴的扫描线， 被扫描线穿过的该下一顶点为当前顶点。 由顶点的下边表的有序及顶点的有序保证了活动边的有序， 因此不需要 每次发扫描线时和所有活动边求交， 然后对交点排序，所以计算量大大减少。

此后进入步骤 204, 根据穿过该当前顶点的当前扫描线和活动边表得到 对应的活动边。 此后进入步骤 205, 根据活动边及奇偶填充法则对当前扫描线穿过的活 动边计数。 在有序活动边表的三角化方法中， 使用奇偶填充规则， 通过只对在当前 扫描线之上的当前顶点的最近左边和最近右边之间的有效区域，组建三角形， 从而进一减少了计算量。 作为本发明的一个优选例， 当前扫描线穿过当前顶点的活动边时， 才对 该活动边及当前扫描线穿过的前一条活动边之间的区域进行计数。

此后进入步骤 206, 找到在当前扫描线之上的当前顶点的最近左边和最 近右边， 其中该最近左边的左方区域的计数为偶数， 该最近左边的右方区域 的计数为奇数， 该最近右边的左方区域的计数为奇数， 该最近右边的右方区 域的计数为偶数。

此后进入步骤 207, 仅在当前扫描线之上且与当前顶点连通又还未被三 角化的有效区域中组建三角形， 最近左边或最近右边的上一顶点中最靠近当 前扫描线的顶点为最近上顶点， 由最近上顶点的扫描线、 当前扫描线、 最近 左边和最近右边确定可以进行三角化的有效区域。 仅在与顶点连通的当前扫 描线之上的有效区域组建三角形， 减少了不必要的三角形切分， 所组成的三 角形数目较少， 形状较大， 大大减少了计算机图形处理部件的计算量， 后续 在三角形基础上的图形处理效率较高。 此后进入步骤 208, 判断该有效区域是否为四边形。 若是， 则进入步骤 209; 否则进入步骤 210。 在步骤 209中， 由穿过该最近上顶点的扫描线、 当前扫描线、 最近左边 和最近右边围成的一个区域， 如果该区域为四边形， 则以对角线将该四边形 划分为两个三角形， 在当前扫描线之上且与当前顶点连通又还未被三角化的 有效区域中组建三角形， 供计算机的图形处理器渲染图像使用。 在当前扫描线之上的当前顶点的最近左边和最近右边之间的有效区域 为三角形或者四边形， 之后， 通过连接四边形的左上顶点与右下顶点或者右 上顶点与坐下顶点形成的对角连线， 将该四边形再次划分为两个三角形， 从 而完成该有效区域的三角化。

在步骤 210中， 分别更新最近左边及最近右边的上端点为各自与当前扫 描线的交点， 对未三角化有效性判断的区域的顶点进行刷新， 为下一次该区 域的三角化有效性判断进行数据准备。 此后进入步骤 21 1 , 从当前活动边表中删除当前顶点的所有上边， 对未 三角化有效性判断的区域顶点的活动边进行刷新， 为下一次该区域的三角化 有效性判断进行数据准备。 此后进入步骤 212, 判断当前顶点是否有下边。 若是， 则进入步骤 213; 否则返回步骤 203, 依次发出穿过经排序的当 前顶点的下一顶点且垂直于指定坐标轴的扫描线， 被扫描线穿过的该下一顶 点为当前顶点。 在步骤 213中， 在最近左边和最近右边之间， 将当前顶点的所有下边依 次插入， 对多边形中未被三角化的剩余区域进行活动边和顶点的有序刷新。 此后进入步骤 214, 判断当前顶点是否为有序活动边表中的最后一个顶 点， 若是， 则结束该多边形三角化流程； 否则返回步骤 203 , 依次发出穿过 经排序的当前顶点下一顶点且垂直于指定坐标轴的扫描线， 被扫描线穿过的 该下一顶点为当前顶点。 在扫描到当前活动边为最后一条边之前， 或者在当前扫描线之上且与当 前顶点连通又还未被三角化的剩余区域都不符合有效区域的条件时， 对于该 多边形中剩余未被三角化的有效区域的确定， 需要在每完成一次的有效区域 三角化之后， 更新该有效区域的最近左边和最近右边的上端点为各自与当前 扫描线的交点， 同时在活动边表中将已进行过三角化的有效区域的活动边删 除， 更新当前活动边表的活动边都是未被扫描过的活动边。 图 3是该计算机图像处理中多边形的三角化方法的流程示意图。 如图 3 所示的该计算机图像处理中多边形的三角化方法， 具体地说： 在步骤 301 中， 根据指定坐标轴的坐标值大小和使用快速排序法， 对多 边形的各个顶点进行排序。 在本发明的某些实施方式中， 对多边形的各个顶点根据指定坐标轴的坐 标值大小进行排序， 其排序方法包括但不限于快速排序法， 也可以包括其他 的排序方法， 比如冒泡排序法， 折半排序法等。 此后进入步骤 302 , 根据经排序的各顶点并按照其所对应的活动边的斜 率大小排序建立活动边表。 相应地， 在活动边表中， 每个顶点所对应的活动边包括但不限于按斜率 大小排序， 若按照斜率进行活动边排序， 则其斜率获取可以通过每条活动边 的一顶点与另一顶点之间的横坐标增量 DX与纵坐标增量 DY的比值 DX/DY 实现， 斜率越小表示越 "右边" ， 斜率越大表示越 "左边" ， 一个顶点发了 扫描线， 并生成完三角形后， 会把其所有已排序的下边， 加入到现有的有序 活动边表， 构成一个新的有序活动边表， 并且已经是排好序的。 这样发扫描 线， 找最近、 最远的边时， 就节省了系统计算工作量， 减少了系统负载， 提 高系统工作效率。 此后进入步骤 303, 依次发出穿过经排序的当前顶点的下一顶点且垂直 于指定坐标轴的扫描线， 被扫描线穿过的该下一顶点为当前顶点。 由顶点的下边表的有序及顶点的有序保证了活动边的有序， 因此每次发 扫描线时不需要和所有活动边求交， 以及对交点排序， 所以计算量进一步减 少。

此后进入步骤 304, 根据穿过该当前顶点的当前扫描线和活动边表得到 对应的活动边。 此后进入步骤 305, 根据活动边及非零填充法则对当前扫描线穿过的活 动边计数。 此后进入步骤 306, 找到在当前扫描线之上的当前顶点的最远左边和最 远右边， 其中该最远左边的左方区域的计数为零， 该最远左边的右方区域的 计数为非零整数， 该最远右边的左方区域的计数为非零整数， 该最远右边的 右方区域的计数为零。 在有序活动边表的三角化方法中， 使用非零填充规则， 通过只对在当前 扫描线之上的当前顶点的最远左边和最远右边之间的有效区域，组建三角形， 从而进一减少了计算量。 此后进入步骤 307, 仅在当前扫描线之上且与当前顶点连通又还未被三 角化的有效区域中组建三角形， 由上一顶点的扫描线、 当前扫描线、 最远左 边和最远右边确定可以进行三角化的有效区域， 其中， 该上一顶点为经排序 的当前顶点的上一顶点。 若判定最远左边的左边区域计数为零且其右边区域的计数为非零整数， 同时最远右边的左边区域的计数为非零整数且其右边区域的计数为零， 则对 最远左边和最近右边之间并且未被确定过有效区域的区域，确定为有效区域。

仅在与顶点连通的当前扫描线之上的有效区域组建三角形， 减少了不必 要的三角形切分， 所组成的三角形数目较少， 形状较大， 大大减少了计算机 图形处理部件的计算量， 后续在三角形基础上的图形处理效率较高。 由穿过上一顶点的扫描线、 当前扫描线、 最远左边和最远右边围成的一 个区域， 其中， 该上一顶点为经排序的当前顶点的上一顶点， 如果该区域为 四边形， 则以对角线将该四边形划分为两个三角形。 此后进入步骤 308, 判断该有效区域是否为四边形。 若是， 则进入步骤 309; 否则进入步骤 310。 在步骤 309中， 以对角线将该四边形划分为两个三角形。 在当前扫描线 之上且与当前顶点连通又还未被三角化的有效区域中组建三角形， 供计算机 的图形处理器渲染图像使用。 在当前扫描线之上的当前顶点的最远左边和最远右边之间的有效区域 为三角形或者四边形， 之后， 通过连接四边形的左上顶点与右下顶点或者右 上顶点与坐下顶点形成的对角线， 将该四边形再次划分为两个三角形， 从而 完成该有效区域的三角化。

在步骤 310中， 分别更新最远左边及最远右边的上端点为各自与当前扫 描线的交点， 对未三角化有效性判断的区域的顶点进行刷新， 为该区域的下 次三角化有效性判断进行数据准备。 此后进入步骤 31 1 , 从当前活动边表中删除当前顶点的所有上边， 对未 三角化有效性判断的区域顶点的活动边进行刷新， 为该区域的下一次三角化 有效性判断进行数据准备。 此后进入步骤 312, 判断当前顶点是否有下边。 若是， 则进入步骤 313; 否则返回步骤 303, 依次发出穿过经排序的当 前顶点的下一顶点且垂直于指定坐标轴的扫描线， 被扫描线穿过的该下一顶 点为当前顶点。 在步骤 313中， 在最远左边和最远右边之间， 将当前顶点的所有下边依 次插入， 对多边形中未被三角化的剩余区域中的活动边和顶点有序刷新。 此后进入步骤 314, 判断当前顶点是否为有序活动边表中的最后一个顶 点。 若是， 则结束该多边形三角化流程； 否则返回步骤 303 , 依次发出穿过 经排序的当前顶点的下一顶点且垂直于指定坐标轴的扫描线， 其中， 被扫描 线穿过的该下一顶点为当前顶点。

在扫描到当前活动边为最后一条边之前， 或者在当前扫描线之上且与当 前顶点连通又还未被三角化的剩余区域都不符合有效区域的判断条件时， 对 于该多边形中剩余未被三角化的区域的有效性判断， 需要在每完成一次的有 效区域三角化之后， 更新该有效区域的最远左边和最远右边的上端点为各自 与当前扫描线的交点， 同时在活动边表中将已进行过三角化的有效区域的活 动边删除， 经更新后的当前活动边表的活动边都是未被扫描过的活动边。 作为本发明的优选例， 图 4是本发明第二实施方式中一种计算机图像处 理中多边形的三角化方法的一种多边形示意图， 活动边表中每个顶点_Vi所对 应的活动边按斜率大小排序时， 只要保证各顶点活动边按照斜率大小排序的 位序方向与穿过经排序的各顶点的扫描线的方向一致即可， 都垂直于指定坐 标轴。 如图 4所示， 假定坐标轴 Y轴为指定坐标轴， 坐标轴 X轴为垂直于 Y 轴的坐标轴， 矢量多边形的顶点根据指定坐标轴 Y轴的方向的坐标值的排序 为 {v₈， v₇, v₉， v₆， v。，_Vl， v₅， v₂， v₃， v₄ }， 在穿过顶点 v。上半区域的三角化有效 性判断之后， 将顶点 V。的下边 {_ei， e₂， e₃， e₄， e₅ }插入有序活动边表使有序活动 边表数据刷新的过程中， 只要保证发出一条平行于坐标轴 X轴的直线 1₁ 依 次与活动边 {_ei， e₂， e₃， e₄， e₅ }相交的顺序进行活动边表中活动边排序的结果， 就为按照活动边的斜率排序的结果， 所求斜率可以直接通过顶点与顶点之间 的位置数值关系进行计算。 奇偶填充和非零填充都是计算机图形学中的术语。 如果扫描线与一个边 相交， 则根据边的方向， 交后的区域 +1或一 1 , 因此不同的区域有不同的值。 奇偶填充指只填奇区域， 不填偶区域。 非零填充指填充所有非零的区域， 不 管是奇区域还是偶区域。 作为本发明的优选例， 图 5 ( 3 )是本发明第二实施方式中一种计算机图 像处理中多边形的三角化方法的一种多边形原始示意图， 经过基于奇偶填充 规则的三角化处理之后， 得到如图 5 ( b ) 所示关于该多边形的效果示意图， 经过基于非零填充规则的三角化处理之后， 得到如图 5 ( c )所示关于该多边 形的效果示意图， 图 6 ( a )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的另一种多边形原始示意图， 其中， 顶点^V2有上边 A, 在其活动边中， 边 A在边 B、 C、 D的左边， 故该顶点 v₂也认为在边 B、 C、 D的左边。 并且， 其下边 F也认为在边 B、 C、 D的左边。 顶点 无上边。 需要与活动边 B和 边 C求交以判断其位置， 该顶点_Vl在边 A和边 D之间。 并且， 其下边边 B 和边 C也会在边 A和边 D之间。 图 6 ( b )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的一种多边形效果示意图， 三角化有效区域的确定采用奇偶填充法则 进行计数， 对于顶点^Vl , 它在边 A和边 D之间， 会找到其最近的左边 A, 且 该边右方区域的计数为奇数； 找到其最近的右边 D, 且该边左方区域值为奇 数。 符合上述条件的边 A和边 D, 会与穿过顶点 的扫描线求交， 得到的交 点 I。和 ^会与顶点 的上一顶点 V。组成三角形， 发送给硬件完成绘制工作， 并 更新交点 I。和 ^分别为边 A和边 D的上端点， 以及将顶点_Vl的下边 B和边 C 插入到边 A和边 D之间， 更新活动边表。 对于顶点 v₂ , 它在最左边， 只需找 到右边 B,该边符合左方区域的计数为奇数且右方区域的计数为偶数的条件， 会与穿过顶点 的扫描线求交， 交点 ι₂ , 并与顶点 i。，_Vl , ι₂组成一个四边形， 该四边形进一步分为两个三角形， 发送给相应硬件处理， 并更新交点 ι₂为边 B的上端点， 以及将顶点 v₂的下边 F插入到边 B的左边用于更新活动边表。 对顶点 v₂来说， 只会生成有效区域 i。_Vl i₂ v₂ , 和边 C及边 D构成的区域不为 有效区域。 图 6 ( c )是本发明第二实施方式中一种计算机图像处理中多边形的三角 化方法的另一种多边形效果示意图， 三角化有效区域的确定采用非零填充法 则进行计数，穿过顶点_Vl的扫描线求交，得到的交点 I。和 ^会与 v。组成三角形， 发送给硬件完成绘制工作， 并更新交点 I。和 ^分别为边 A和边 D的上端点， 以及将顶点_Vl的下边 B和边 C插入到边 A和边 D之间， 更新活动边表。 对 于顶点 v₂ , 它在最左边， 只需找到最远右边 D, 该边符合左方区域的计数为 非零整数， 右边区域的计数为零的条件， 且距离 v₂最远。 会穿过顶点 v₂的扫 描线求交， 交点 ι₃ , 并与顶点 i。， v₂组成一个四边形， 该四边形进一步分 为两个三角形， 发送给相应硬件处理， 并更新交点 1₃为边 D的上端点， 以及 将顶点 v₂的下边 F插入到边 B的左边用于更新活动边表。 对 来说， 只会生 成有效区域 ι₃ ι₀ ν₂ , 边 B和边 C构成的区域不会再额外生成三角形。 在本发明的其他实施方式中， 包括但不限于以非零或者奇偶的方式进行 三角化有效区域的确定， 也可以以其他渲染规则进行， 比如左上填充、 马赛 克处理等。 本发明的各方法实施方式均可以以软件、 硬件、 固件等方式实现。 不管 本发明是以软件、 硬件、 还是固件方式实现， 指令代码都可以存储在任何类 型的计算机可访问的存储器中 （例如永久的或者可修改的， 易失性的或者非 易失性的， 固态的或者非固态的， 固定的或者可更换的介质等等） 。 同样， 存储器可以例如是可编程阵列逻辑 （ Programmable Array Logic , 筒称 "PAL" ) 、 随机存取存储器（Random Access Memory, 筒称 " RAM" ) 、 可编程只读存储器（ Programmable Read Only Memory, 筒称 "PROM" ) 、 只读存储器（Read-Only Memory, 筒称 "ROM" ) 、 电可擦除可编程只读 存储器（Electrically Erasable Programmable ROM , 筒称 "EEPROM" ) 、 磁盘、 光盘、 数字通用光盘 （ Digital Versatile Disc, 筒称 "DVD" ) 等等。 本发明第三实施方式涉及一种计算机图像处理中多边形的三角化系统。 图 7是该计算机图像处理中多边形的三角化系统的结构示意图。 该计算机图 像处理中多边形的三角化系统包括以下模块： 排序模块， 用于对多边形的各个顶点根据指定坐标轴的坐标值大小进行 排序。 建表模块， 用于根据经排序模块排序的各顶点建立活动边表。 扫描模块， 用于依次发出穿过经排序模块排序的各顶点且垂直于指定坐 标轴的扫描线。 获取模块， 用于对于扫描模块发出的每一条穿过当前顶点的当前扫描 线， 根据建表模块建立的活动边表得到对应的活动边。 计数模块， 用于对于扫描模块发出的每一条穿过当前顶点的当前扫描 线， 对当前扫描线穿过的活动边进行计数。 确定模块， 用于根据计数模块得到的计数， 确定获取模块获取的各活动 边之间区域的有效性。 组建模块， 用于仅在当前扫描线之上且与当前顶点连通又还未被三角化 的有效区域中组建三角形， 供计算机的图形处理器渲染图像使用。 在本发明的其他某些实施方式中， 扫描模块可以每发出一条扫描线， 就 对该扫描线之上且在未被三角化的有效区域中组建三角形， 也可以先就多边 形的所有顶点全部出扫描线， 再对每一条扫描之上且在未被三角化的有效区 域中组建三角形。

第一实施方式互相配合实施。 第一实施方式中提到的相关技术细节在本实施 方式中依然有效， 为了减少重复， 这里不再赘述。 相应地， 本实施方式中提 到的相关技术细节也可应用在第一实施方式中。 本发明第四实施方式涉及一种计算机图像处理中多边形的三角化系统。 图 8和图 9是该计算机图像处理中多边形的三角化系统的结构示意图。 第四实施方式在第三实施方式的基础上进行了改进， 主要改进之处在 于： 根据不同的填充法则， 增加了相应的子模块。 排序模块使用快速排序法 对各个顶点进行排序。活动边表中每个顶点所对应的活动边按斜率大小排序。 具体地说： 如图 8所示， 组建模块还包括以下子模块：

最近边获取子模块， 用于找到在当前扫描线之上的当前顶点的最近左边 和最近右边， 其中该最近左边的左方区域的计数为偶数， 该最近左边的右方 区域的计数为奇数， 该最近右边的左方区域的计数为奇数， 该最近右边的右 方区域的计数为偶数。 第一生成子模块， 用于由穿过最近上顶点的扫描线、 当前扫描线、 最近 边获取模块获取的最近左边和最近右边围成一个区域， 其中， 最近边获取模 块获取的最近左边或最近右边的上一顶点中最靠近当前扫描线的顶点为最近 上顶点。 第一划分子模块， 用于如果区域生成模块生成的区域为四边形， 则以对 角线将该四边形划分为两个三角形。 如图 9所示， 组建模块还包括以下子模块：

最远边获取子模块， 用于找到在当前扫描线之上的当前顶点的最远左边 和最远右边， 其中该最远左边的左方区域的计数为零， 该最远左边的右方区 域的计数为非零整数， 该最远右边的左方区域的计数为非零整数， 该最远右 边的右方区域的计数为零。 第二生成子模块， 用于由穿过上一顶点的扫描线、 当前扫描线、 最远边 获取模块获取的最远左边和最远右边围成一个区域， 其中， 该上一顶点为经 排序的当前顶点的上一顶点。 第二划分子模块， 用于如果区域生成模块生成的区域为四边形， 则以对 角线将该四边形划分为两个三角形。

第二实施方式互相配合实施。 第二实施方式中提到的相关技术细节在本实施 方式中依然有效， 为了减少重复， 这里不再赘述。 相应地， 本实施方式中提 到的相关技术细节也可应用在第二实施方式中。 在对矢量化图形进行处理的过程中， 为了提高矢量化图像转换后的数据的 压缩率， 节省压缩计算量， 本发明实施例中， 对差分编码技术进行了优化， 从 而重新设计出一种压缩算法， 具体为： 采用扫描线将待处理的矢量图形切分为 若干图元， 以及分别确定每一条扫描线切分获得的图元， 记录每一条扫描线的 纵坐标， 并确认任意一图元在其对应的扫描线上的顶点， 与该扫描线具有相同 纵坐标， 接着， 再分别根据每一个图元在其对应的扫描线上的顶点， 确定相应 图元的基准点， 并分别基于每一个图元的基准点的坐标， 以差分编码形式记录 相应图元各顶点的坐标。

下面结合附图对本发明优选的实施方式进行详细说明。

参阅图 11A所示， 本发明实施例中， 图形压缩装置包括切分单元 10、 第一处 理单元 11和第二处理单元 12, 其中，

切分单元 10, 用于采用扫描线将待处理的矢量图形切分为若干图元； 第一处理单元 11 , 用于分别确定每一条扫描线切分获得的图元， 记录每一 条扫描线的纵坐标， 并确认任意一图元在其对应的扫描线上的顶点， 与该扫描 线具有相同纵坐标；

第二处理单元 12, 用于分别根据每一个图元在其对应的扫描线上的顶点， 确定相应图元的基准点， 并分别基于每一个图元的基准点的坐标， 以差分编码 形式记录相应图元各顶点的坐标。

基于上述技术方案， 参阅图 11B所示， 通常情况下， 在对矢量图形进行压缩 前， 需要先将其转换为三角形数据， 较佳的， 可以采用活动边表三角化算法， 将任意一种矢量图形分解为以下图元： 梯形， 上三角 （即顶点在底边之上）和 下三角 （即顶点在底边之下； 进一步地， 也可以再将梯形切分为两个三角形。 以对 flash文件解析后的结果为例，将 flash文件解析后获得的三角化数据包含的梯 形、 上三角和下三角等图元中， 梯形的数目占图元总数目的 90%, 其中， 像素大 小小于 1个像素的梯形或三角形占图元总数目的 40 %。

由此可见， 将矢量图形解析为三角形数据后， 其包含大部分数值比较接近， 适合于用差分压缩算法来做。

那么， 参阅图 1230所示， 本发明实施例中， 对矢量图形进行三角形数据压 缩的详细流程: ¾口下：

步骤 30: 采用扫描线将待处理的矢量图形切分为若干图元， 即将待处理的 矢量图形解析为三角形数据。

例如， 参阅图 2所示， 多条彼此平行的扫描线将矢量图形分解为若干图元， 其中， 分解获得的图元可以包含梯形、 上三角形和下三解形中的任意一种或任 意组合。

本发明实施例中， 三角形数据只是一种举例， 实际应用中， 针对其他类似 的数据也可以采用类似的压缩方法， 在此不再赘述。

步骤 31 : 分别确定每一条扫描线切分获得的图元， 记录每一条扫描线的纵 坐标， 并确认任意一图元在其对应的扫描线上的顶点， 与该扫描线具有相同纵 坐标。

本实施例中， 设定由同一扫描线切分获得的所有图元的下顶点坐标的 y值都 相同， 即每两条平行且相邻的扫描线切分出的各图元均以下扫描线的 y值作为自 身下顶点坐标的 y值。

当然， 实际应用中， 也可以设定所有图元的上顶点坐标的 y值均相同， 即每 两条平行且相邻的扫描线切分出的各图元均以上扫描线的 y值作为自身上顶点 坐标的 y值， 本实施例中仅以前一种情况为例进行介绍。

通常情况下， 三角化数据是定点化为小数点后 10位的整数， 在硬件处理中 保留至小数点后 5位即可； 针对这一特点， 本实施例中， 以任意一条扫描线切分 获得的所有图元为例， 介绍具体压缩后的数据存储格式如下：

在执行步骤 310时， 针对任意一条扫描线切分获得的所有图元， 首先， 可以 用 lbyte (字节）存储图元（梯形， 上三角， 下三角） 的数目， 并用这 lbyte最高 位的 lbit (比特）表示上述任意一扫描线的 y值所占用的字节数， 如， 0表示 y值 占 2byte, 1表示 y值占 3byte;

接着用 2 ~ 3个 byte存储上述任意一扫描线的 y值，较佳的，可以采用 11.5格式 存储扫描线的 y值， 所谓 11.5格式即是采用 16bits表示该 y值， 其中， 前 l lbits表示 y值的整数部分， 后 5bits表示 y值的小数部分。 由于预先存储了扫描线的 y值， 并 且该扫描线切分获得的所有图元的下顶点均与该扫描线具有相同纵坐标， 因此， 后续在存储下顶点的坐标时， 可以不用保存 y值， 从而节省了计算量， 也提高了 压缩率。

步骤 32: 分别根据每一个图元在其对应的扫描线上的顶点， 确定相应图 元的基准点。

例如， 针对任意一条扫描线切分获得的任意一个图元， 可以选定该图元 的左下顶点为基准点， 此时， 可以记录该基准点的横坐标值， 基准点的纵坐标 值即为切分出该图元的扫描线的纵坐标， 已预先记录， 因此， 此处可以不再重 复记录。

当然， 除了这种情况外， 也可以选用图元的右下顶点、 左上顶点、 右上顶 点为基准点， 本实施例仅以最为节省计算量的左下顶点为例进行介绍， 但并不 述。

步骤 33 : 分别基于每一个图元的基准点的坐标， 以差分编码形式记录相应 图元各顶点的坐标。

仍然以同一扫描线切分获得的所有图元为例， 这些图元的下顶点 （包括左 下顶点或 /和右下顶点） 的 y值均与相应的扫描线的 y值相同， 由于各扫描线的 y 值均预先按照步骤 31记载的方式进行了记录， 因此， 在进行图元数据压缩时， 无需再次记录图元下顶点的 y值。

下面以同一扫描线切分获得的所有图元中任意一图元为例， 介绍步骤 33的 具体执行方式如下：

第一种情况， 若上述任意一图元为梯形， 则执行步骤 33的方式为：

Al、 记录梯形左下顶点的 X值， 即先确定基准点的 X值， 此时， 默认基准点 的 y值为相应扫描线的 y值， 无需重复记录；

Bl、记录梯形的右下顶点 X值与基准点 X值的差值，记为 Δ右下顶点 X,此时， 也默认右下顶点的 y值为相应扫描线的 y值， 即与基准点的 y值相同， 无需重复记 录；

Cl、 记录梯形的右上顶点 X值与基准点 X值的差值， 记为 Δ右上顶点 X；

Dl、 记录梯形的右上顶点 y值与基准点 y值的差值， 记为 右上顶点 y;

El、 记录梯形的左上顶点 x值与基准点 x值的差值， 记为 Δ左上顶点 X；

Fl、 记录梯形的左上顶点 y值与基准点 y值的差值， 记为 Δ左上顶点 。

至此， 梯形四个顶点的坐标均已确定， 那么表示梯形这一图元的相关数据 已压缩完毕， 按照这些记录， 可以准确地确定出梯形的形状和位置。

第二种情况， 若上述任意一图元为上三角形， 则执行步骤 33的方式为： A2、 记录上三角形左下顶点的 X值， 即先确定基准点的 X值， 此时， 默认基 准点的 y值为相应扫描线的 y值， 无需重复记录；

B2、 记录上三角形的右下顶点 X值与基准点 X值的差值， 记为 右下顶点 X, 此时， 也默认右下顶点的 y值为相应扫描线的 y值， 即与基准点的 y值相同， 无需 重复记录；

C2、 记录上三角形的左上顶点 X值与基准点 X值的差值， 记为 Δ左上顶点 X；

D2、 记录上三角形的左上顶点 y值与基准点 y值的差值， 记为 Δ左上顶点 。 由于上三角形仅有一个上顶点， 因此可以将其以左上顶点的形式记录 ， 也 可以将其以右上顶点的形式记录， 本实施例中仅以前一种情况为例进行介绍， 并不局限于此。

至此， 上三角形三个顶点的坐标均已确定， 那么表示上三角形这一图元的 相关数据已压缩完毕， 按照这些记录， 可以准确地确定出上三角形的形状和位 置。

第三种情况， 若上述任意一图元为下三角形， 则执行步骤 33的方式为： A3、 记录下三角形左下顶点的 X值， 即先确定基准点的 X值， 此时， 默认基 准点的 y值为相应扫描线的 y值， 无需重复记录；

B3、 记录下三角形的右上顶点 X值与基准点 X值的差值， 记为 右上顶点 X； C3、 记录下三角形的右上顶点 y值与基准点 y值的差值， 记为 Δ右上顶点 y; D3、 记录下三角形的左上顶点 x值与基准点 x值的差值， 记为 Δ左上顶点_x。

E3、 记录下三角形的左上顶点 y值与基准点 y值的差值， 记为 Δ左上顶点 。 由于下三角形仅有一个下顶点， 因此可以直接将下顶点以基准点 （即左下 顶点） 的形式记录， 当然， 也可以将其以右下顶点的形式记录， 本实施例中仅 以前一种情况为例进行介绍， 并不局限于此。

至此， 下三角形三个顶点的坐标均已确定， 那么表示下三角形这一图元的 相关数据已压缩完毕， 按照这些记录， 可以准确地确定出下三角形的形状和位 置。

基于上述实施例， 针对任意一个图元（梯形、 上三角形、 下三解形均可）， 可以采用以下方式记录其相应的差分数据：

用 2个 byte表示上述任意一个图元的信息。

对于第一个 byte:

第 0~lbit表示△右上顶点 X所占的 byte数。

第 2~3bit表示△右下顶点 X所占的 byte数。

第 4bit表示基准点的 X值所占的 byte数； 其中， 0表示占用 2byte, 1表示占用 3 个 byte。

第 6~7bit表示图元的类型： 0为梯形， 1为上三角形， 2为倒三角形。

对于第二个 byte:

第 2~3bit表示△左上顶点 y占用的 byte数。

第 4~5bit表示 左上顶点 X占用的 byte数。 - - 丁^^碑 ι^^ ffi f ^^ ^碑 一舍^ ' ^ w ^

60^x0'l l X0'60^x0'l l X0'%x0'8lX0'00^x0

： (

(6ί^ΐ6000^χ0 'q8 9000^x0 )'(φ^ΐ6000^χ0 'S8 9000^X0 )'(6ί^βΐ6000^χ0 '0061^000^χ0) (Φ^ΐ6000^χ0 'S8 9000^X0 )'(φ^ΐ6000^χ0 '0061^000^χ0 )'(6ί^βΐ6000^χ0 '0061^000^χ0) (Φ^ΐ6000^χ0 'S8 9000^X0 )'(6^Ρΐ6000^χ0 ' q99000^x0 )'(φ^ΐ6000^χ0 '0061^000^χ0) (6^Ρΐ6000^χ0 ' iq99000^x0 )'(6^Ρΐ6000^χ0 '&JO OOO^xO )'(φ^ΐ6000^χ0 '006l7S000^x0) ： (^古

90^χ0'00^χ0' 8^χ0'90^χ0' ΐ 0^Χ0'09^Χ0' ΐΟ^χθ'ΐ 6^x0'S^0' ΐ χθ'ΐ 9^χθ'^βΟ^χθ'6ΐΧθ'^βΑ^χθ' ΐ 0^Χ0

： (

(Β«

(eooe 古

ΐ0^χ0Ό0^χ0'Ρ9^χ0Ό0^χ0'¾^χ0'9ζ^χ0'ΐΑΧ0Ί ^0'8ΐΧ0'6ΐΧ0'88^χ0'ΐ0^χ0

:( ½¥

(en 60oo^xo '(6 ε6000^χ0 ' 33ςοθΟ^χΟ ) ' ( u 6000^x0 '

:丄4 ( ^^¥Ρ^10/ΑΥΔ ) 丄。 f辨 ^ ¾τ τ丁 '。fi ^^ ^ ^mn^ ' ^ ^ ^ ？？丁 t±r

09C980/ZT0ZN3/X3d S96980/CT0Z OAV 顶点的纵坐标均相同的特点， 首先存储了每条扫描线切分得到的图元的数目和 每条扫描线的纵坐标， 然后以每个图元在相应扫描线上的某一顶点为基准点， 根据每一个图元的基准点的坐标， 依次存储相应图元各顶点的坐标值和基准点 坐标值的差值， 较佳的， 所有坐标值均以定点数 11.5的格式存储， 这样， 便优化 地完成了数据的压缩操作， 节省了针对同样的图形多次做压缩所带来的计算性 能上的开销， 同时提高了数据的压缩率， 在提高编码效率的同时， 减少了对计 算机系统的存储空间的占用。 特别是在图元数量非常庞大的时候， 这种方法可 比现有技术节省 20%-30%的内存空间， 也更适合用于存储空间比较有限的嵌入 式计算机系统中。 在本发明的一个优选实施方式中提出了一种计算机图像处理中对矢量化图 形进行数据压缩的方法， 包括以下步骤：

采用扫描线将待处理的矢量图形切分为若干图元。 其中可以采用第一或第 二实施方式提出的多边形三角化方法将矢量图形切分为若干三角形。

分别确定每一条扫描线切分获得的图元， 记录每一条扫描线的纵坐标， 并 确认任意一图元在其对应的扫描线上的顶点与该扫描线具有相同纵坐标。 本步 骤中， 可以是确认由同一扫描线切分获得的所有图元的下顶点的纵坐标均为该 扫描线的纵坐标； 或者， 确认由同一扫描线切分获得的所有图元的上顶点的纵 坐标均为该扫描线的从坐标。

分别根据每一个图元在其对应的扫描线上的顶点， 确定相应图元的基准点。 本步骤中， 将所述任意一图元的左下顶点确定为该任意一图元的基准点； 或者， 将所述任意一图元的右下顶点确定为该任意一图元的基准点。

分别基于每一个图元的基准点的坐标， 以差分编码形式记录相应图元各顶 点的坐标。

若将所述任意一图元的左下顶点确定为基准点， 且该任意一图元为梯形， 则基于所述基准点的坐标， 以差分编码形式记录所述任意一图元各顶点的坐标 的步骤包括以下子步骤：

记录所述梯形的基准点的横坐标， 并确定所述基准点的纵坐标为所述任意 一图元对应的扫描线的从坐标；

记录所述梯形的右下顶点的横坐标与基准点的横坐标的差值， 并确定所述 右下顶点的纵坐标与所述基准点的纵坐标相同；

记录所述梯形的右上顶点的横坐标与基准点的横坐标的差值；

记录所述梯形的右上顶点的纵坐标与基准点纵坐标的差值；

记录所述梯形的左上顶点的横坐标与基准点的横坐标的差值；

记录所述梯形的左上顶点的纵坐标与基准点的纵坐标的差值。

若将所述任意一图元的左下顶点确定为基准点， 且该任意一图元为上三角 形， 则基于所述基准点的坐标， 以差分编码形式记录所述任意一图元各顶点的 坐标的步骤包括以下子步骤：

记录所述上三角形基准点的横坐标， 并确认所述基准点的纵坐标为相应扫 描线的纵坐标；

记录所述上三角形的右下顶点的横坐标与基准点的横坐标的差值， 并确认 所述右下顶点的纵坐标与基准点的纵坐标相同；

记录所述上三角形的左上顶点的横坐标与基准点的横坐标的差值； 记录所述上三角形的左上顶点的纵坐标与基准点的纵坐标的差值。

若将所述任意一图元的左下顶点确定为基准点， 且该任意一图元为下三角 形， 则基于所述基准点的坐标， 以差分编码形式记录所述任意一图元各顶点的 坐标的步骤包括以下子步骤：

记录所述下三角形基准点的横坐标， 并确认所述基准点的纵坐标为相应扫 描线的纵坐标；

记录所述下三角形的右上顶点的横坐标与基准点的横坐标的差值； 记录所述下三角形的右上顶点的纵坐标与基准点的纵坐标的差值； 记录所述下三角形的左上顶点的横坐标与基准点的横坐标的差值； 记录所述下三角形的左上顶点的纵坐标与基准点的纵坐标的差值。

本发明的一个优选实施方式还提出了一种在计算机图像处理中对矢量 化图形进行数据压缩的装置， 包括： 切分单元， 用于采用扫描线将待处理的矢量图形切分为若干图元。 优选 地， 该切分单元可以采用第三或第四实施方式所公开的三角化系统。 第一处理单元， 用于分别确定每一条扫描线切分获得的图元， 记录每一 条扫描线的纵坐标， 并确认任意一图元在其对应的扫描线上的顶点与该扫描 线具有相同纵坐标。 该第一处理单元具体用于： 在确认任意一图元在其对应 的扫描线上的顶点， 与该扫描线具有相同纵坐标时， 确认由同一扫描线切分 获得的所有图元的下顶点的纵坐标均为该扫描线的纵坐标， 或者， 确认由同 一扫描线切分获得的所有图元的上顶点的纵坐标均为该扫描线的纵坐标。 第二处理单元， 用于分别根据每一个图元在其对应的扫描线上的顶点， 确定相应图元的基准点， 并分别基于每一个图元的基准点的坐标， 以差分编 码形式记录相应图元各顶点的坐标。 该第二处理单元具体用于： 若所述第一处理单元确认由同一扫描线切 分获得的所有图元的下顶点的纵坐标均为该扫描线的纵坐标， 则所述第二处 理单元根据所述任意一图元的下顶点， 确定所述任意一图元的基准点时， 将 所述任意一图元的左下顶点确定为该任意一图元的基准点， 或者， 将所述任 意一图元的右下顶点确定为该任意一图元的基准点。 或者， 所述第二处理单元具体用于： 若所述第二处理单元将所述任意一 图元的左下顶点确定为基准点， 且该任意一图元为梯形， 则所述第二处理单 元基于所述基准点的坐标， 以差分编码形式记录所述任意一图元各顶点的坐 标时， 包括： 记录所述梯形的基准点的横坐标， 并确定所述基准点的纵坐标为所述任 意一图元对应的扫描线的纵坐标； 记录所述梯形的右下顶点的横坐标与基准点的横坐标的差值， 并确定所 述右下顶点的纵坐标与所述基准点的纵坐标相同； 记录所述梯形的右上顶点的横坐标与基准点的横坐标的差值； 记录所述梯形的右上顶点的纵坐标与基准点纵坐标的差值；

记录所述梯形的左上顶点的横坐标与基准点的横坐标的差值； 记录所述梯形的左上顶点的纵坐标与基准点的纵坐标的差值。

或者， 所述第二处理单元具体用于： 若所述第二处理单元将所述任意一图元的左下顶点确定为基准点， 且该 任意一图元为上三角形， 则所述第二处理单元基于所述基准点的坐标， 以差 分编码形式记录所述任意一图元各顶点的坐标， 包括： 记录所述上三角形基准点的横坐标， 并确认所述基准点的纵坐标为相应 扫描线的纵坐标； 记录所述上三角形的右下顶点的横坐标与基准点的横坐标的差值， 并确 认所述右下顶点的纵坐标与基准点的纵坐标相同； 记录所述上三角形的左上顶点的横坐标与基准点的横坐标的差值； 记录所述上三角形的左上顶点的纵坐标与基准点的纵坐标的差值。 或者， 所述第二处理单元具体用于： 若所述第二处理单元将所述任意一图元的左下顶点确定为基准点， 且该 任意一图元为下三角形， 则所述第二处理单元基于所述基准点的坐标， 以差 分编码形式记录所述任意一图元各顶点的坐标， 包括： 记录所述下三角形基准点的横坐标， 并确认所述基准点的纵坐标为相应 扫描线的纵坐标； 记录所述下三角形的右上顶点的横坐标与基准点的横坐标的差值； 记录所述下三角形的右上顶点的纵坐标与基准点的纵坐标的差值； 记录所述下三角形的左上顶点的横坐标与基准点的横坐标的差值； 记录所述下三角形的左上顶点的纵坐标与基准点的纵坐标的差值。 需要说明的是， 本发明各系统和设备实施方式中提到的各模块都是逻辑 模块， 在物理上， 一个逻辑模块可以是一个物理模块， 也可以是一个物理模 块的一部分， 还可以以多个物理模块的组合实现， 这些逻辑模块本身的物理 实现方式并不是最重要的， 这些逻辑模块所实现的功能的组合是才解决本发 明所提出的技术问题的关键。 此外， 为了突出本发明的创新部分， 本发明上 述各设备实施方式并没有将与解决本发明所提出的技术问题关系不太密切的

虽然通过参照本发明的某些优选实施方式， 已经对本发明进行了图示和 描述， 但本领域的普通技术人员应该明白， 可以在形式上和细节上对其作各 种改变， 而不偏离本发明的精神和范围。