CN101046892A - 图形描绘设备 - Google Patents

Abstract

通过管理处理顺序和数据，其中所述处理顺序和数据都与包括在将成为输入的矢量数据组中的待处理矢量有关；根据管理信息从将成为输入的矢量数据组中提取和待处理数据有关的数据；计算提取的矢量数据的处理顺序；通过使用计算的处理顺序信息，通告待处理目标点的管理，和目标矢量的处理的结束；根据和待处理目标点有关的管理信息，确定待处理目标点的填充是否能够实现，从而计算填充信息；和利用计算的填充信息描绘图形。

Description

图形描绘设备

技术领域

本发明涉及图形描绘设备和图形描绘方法。

背景技术

已提出描绘任意多边形的各种方法。这些方法包括(1)基于点的方法，(2)基于光栅线的方法，(3)基于三角形的方法，和(4)基于模板缓存的方法。

方法(1)是关于包括在描绘区中的各个点(像素)确定描绘，并基于每个点(像素)进行描绘操作的方法。为了加快描绘(rendering)操作，想到了各种方案，比如删除无用的描绘区，或者简化在每个点的图案(drawing)的确定。但是，为了实现描绘方面的加速，通常以硬件的形式体现该功能。其中以硬件形式体现方法(1)的一种设备被称为光栅器(rasterizer)(例如，参见下面列出的背景文献1)。该方法简单，从而其特点在于操作非常稳定，但是缺点是必须确定每个点的描绘，从而引起很高的处理成本。为此，该功能通常被体现为定制设计的硬件。

方法(2)对应于方法(1)的改进。方法(2)类似于方法(1)，因为基于每个点或者在与每个点对应的范围内确定图案。但是，当进行描绘时，各个点中的描绘部分被集中，并用希望在其上实现描绘的屏幕的各个扫描线的绘线图替换这样集中的描绘部分。从而，对于图案的确定，如同方法(1)一样，方法(2)也引起高的处理成本。但是，描绘操作的成本被缩减，从而方法(2)预期比方法(1)快。确定图案必须伴有由具有高速CPU的处理系统执行的处理，或者呈定制设计硬件形式的处理的实现。通用图形LSI(GPU)可被用于描绘操作。其原因在于图形LSI具有高速描绘线条和三角形的功能。为此，可以说与方法(1)相比，方法(2)的通用性提高。

方法(3)把希望绘制的多边形分成一组三角形，并用三角形描绘多边形(例如参见下面列出的背景文献2)。方法(3)意图是在使用通用图形LSI或者高速三角形化描绘设备的前提下实现加速(因为图形LSI具有高速描绘线条和三角形的功能)。于是，在通用性方面，方法(3)优于方法(1)和(2)。但是，三角形化要求复杂的处理，从而复杂处理的稳定性会成为问题。当希望绘制的多边形形状非常复杂时，还会出现成本很高的三角形化处理的问题。由于方法(3)建立在利用图形LSI等来描绘一组三角形的前提上，因此当LSI资源不足时，LSI不能被使用。原因在于多边形必须被分成一组三角形；这样分割的三角形必须被送给图形LSI，图形LSI又造成存储器使用量的明显增大。

方法(4)完全以通用图形LSI的使用为基础，通过使用图形LSI中提供的称为模板缓存的功能，实现多边形描绘(例如参见下面列出的背景文献3)。与方法(1)-(3)任意之一相比，方法(4)能够实现更稳定和更快的多边形描绘。但是，方法(4)必然伴有图形LSI的特征的充分使用，从而出现需要图形LSI的大量资源的问题。

背景文献1：

Renate Kempf和Chris Frazier，“The Open GL ProcessingPipeline”，Chapter 2：Overview of Commands and Routines，Open GLReference Manual Second Edition，ISBN 0-201-46140-4，pp.8-16，1997。

背景文献2：

Mark de Berg，Mare van Kreveld，Mark Overmars和OtfriedSchwartzkopf，“Computational Geometry”，ISBN 4-7649-0277-X，pp.55-75，Kindai Kagakusha Co.，Ltd.，2000。

背景文献3：

Jackie Neider，Tom Davis，Mason Woo，“Drawing filled，Concave Polygons Using the Stencil Buffer”，Chapter 13：Now ThatYou Know，OpenGL programming Guide，ISBN 0-201-63274-8，pp.398-399，1993。

发明内容

本发明的目的之一是提供一种图形描绘设备和图形描绘方法，所述设备和方法能够在资源使用量较低的情况下，实现高速、稳定的操作。具体地说，本发明提供一种图形描绘设备和图形描绘方法，所述设备和方法通过使用能够实现尽可能稳定的操作的简单方法，可在图形LSI等的硬件资源的使用方面遇到困难的情况下，实现可能的最快操作。

根据本发明的第一方面，提供一种图形描绘设备，包括：矢量数据组管理单元，用于根据第一管理信息，管理包括各组矢量数据的矢量数据组；矢量数据提取单元，用于根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；处理顺序计算单元，用于计算矢量数据提取单元提取的矢量数据的处理顺序；目标点管理单元，通过根据处理顺序确定待处理的目标点，产生用于管理目标点的第二管理信息，并通知矢量数据组管理单元目标矢量的处理已结束；填充信息计算单元，用于根据第二管理信息确定目标点是否将被填充，和计算指示确定结果的填充信息；和描绘单元，用于使用填充信息描绘多边形。

根据本发明的第二方面，提供一种图形描绘设备，包括：矢量数据组管理单元，用于根据第一管理信息，管理包括各组矢量数据的矢量数据组；矢量数据提取单元，用于根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；起点-终点计算单元，用于根据矢量数据提取单元提取的矢量数据，计算指示处理的起点和终点的起点-终点信息；目标点管理单元，通过根据起点-终点信息确定待处理的目标点，产生用于管理目标点的第二管理信息，并通知矢量数据组管理单元目标矢量的处理已结束；目标点计算单元，用于根据第二管理信息计算待处理目标点的像素的坐标；目标点确定单元，用于确定是否将填充位于待处理目标点的坐标两侧的像素；填充信息计算单元，用于根据填充信息确定单元的确定结果，计算关于目标点的填充信息；填充信息存储单元，用于保存填充信息；填充信息记录单元，用于把填充信息计算单元计算的填充信息记录到填充信息存储单元中；描绘区域计算单元，用于根据矢量数据提取单元提取的矢量数据，计算和更新将描绘多边形的描绘区域；描绘区域修正单元，通过对描绘区域计算单元计算的描绘区域进行修正，产生描绘区域信息；描绘数据修正单元，通过对保存在填充信息存储单元中的填充信息进行修正，产生对描绘来说最佳的数据；和描绘单元，通过使用描绘区域信息和描绘数据修正单元产生的数据，描绘多边形。

根据本发明的第三方面，提供一种图形描绘方法，包括：管理包括在矢量数据组中的多组矢量数据的处理顺序；根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；计算提取的矢量数据的处理顺序；根据第二管理信息和计算的处理顺序，管理待处理的目标点；通知目标矢量的处理的结束；根据第二管理信息确定目标点是否将被填充；计算指示该确定结果的填充信息；和使用计算的填充信息描绘多边形。

附图说明

附图中：

图1是表示根据本发明的一个实施例的图形描绘设备的例证结构的示意图；

图2是描述矢量数据组的图；

图3是描述图形描绘的图；

图4是描述图形描绘的图；

图5是描述一个多边形图形的图；

图6是描述一个未闭合多边形图形的图；

图7是描述一个多边形图形的图；

图8是描述矢量数据组管理单元的处理流程的图；

图9是描述起点-终点计算单元的处理流程的图；

图10A-10C是描述起点和终点的计算的示意图；

图11是表示连续矢量所共有的一点的双重处理的图；

图12是描述目标点管理单元的处理流程的图；

图13是确定填充区域的流程图；

图14是描述对于每条扫描线的图形描绘操作的图；

图15是描述对于每条扫描线的图形描绘操作的图；

图16是描述对于每条扫描线的图形描绘操作的图；

图17是描述填充信息存储区的图；

图18是描述描绘区域的图；

图19是描述描绘区域的图；

图20是描述描绘区域的图；

图21是计算流程图；

图22是描述对描绘区的修正的图；

图23是描述对描绘数据的修正的图；

图24是描绘单元的处理流程图；

图25是表示根据本发明的实施例的第一改进的图形描绘设备的例证结构的示意图；

图26是表示根据本发明的实施例的第二改进的图形描绘设备的例证结构的示意图；

图27是表示根据本发明的实施例的第三改进的图形描绘设备的例证结构的示意图；

图28是表示根据本发明的实施例的第四改进的图形描绘设备的例证结构的示意图；

图29是描述对填充信息的修正的图；

图30是描述对填充信息的修正的图；

图31是描述对填充信息的修正的图。

具体实施方式

下面参考附图说明本发明的实施例。

图形描绘设备的总体结构

图1是是根据本发明的实施例的图形描绘设备的整体的方框图。

根据该实施例的图形描绘设备包括：矢量数据组管理单元1，用于管理将成为输入的矢量数据组；矢量数据提取单元2，用于根据在矢量数据组管理单元1中采用的管理信息，从将成为输入的矢量数据组中提取待处理的矢量数据；起点-终点计算单元3，用于根据矢量数据提取单元2提取的矢量数据，计算处理的起点和终点；目标点管理单元4，用于通过使用起点-终点计算单元3计算的起点-终点信息，和/或与从填充信息计算单元7获得的目标点的处理已结束的通知信息，确定待处理的目标点，以及用于向矢量数据组管理单元1通知目标向量的处理已结束；目标点计算单元5，用于根据和目标点管理单元4确定的待处理目标点有关的信息，计算待处理目标点的像素的坐标；目标点确定单元6，用于确定是否在目标点计算单元5计算的待处理目标点的坐标的两侧填充像素；填充信息计算单元7，用于根据目标点确定单元6的确定结果，确定目标点是填充起点，填充终点，还是两者都不是，并把该目标点连同目标点的坐标一起计算为预定格式的填充信息；填充信息记录单元8，用于把填充信息计算单元7计算的填充信息记录到填充信息存储区9中；描绘区域计算单元10，用于根据矢量数据提取单元2提取的矢量数据，计算和更新与描绘某一图形所需的最小矩形区域有关的信息；描绘区域修正单元11，用于对描绘区域计算单元10计算的矩形区域进行修正，从而确定最终将进行描绘的区域；描绘数据修正单元12，用于把保存在填充信息存储区9中的填充信息修正为对描绘来说最佳的数据；和描绘单元13，用于通过使用从描绘区域修正单元11获得的描绘区域信息，和描绘数据修正单元12修正的数据，描绘图形。

矢量数据组管理单元

下面将说明矢量数据组管理单元1。

图形描绘的说明

现在说明关于该实施例描述的图形描绘。在本实施例中描述的图形描绘用于通过使用由形成多边形的矢量数据组或者对应于多边形的点数据组形成的输入数据，描绘由输入数据指示的多边形形成的图形。此时，所述图形的内部按照预定的规则被填充。

具体地说，假定已输入形成“多边形”的矢量数据组(通过单一笔划(writing stroke)获得)，例如图2中所示的“矢量1”～“矢量5”，那么如图3和4中所示的图形被描绘。图3和图4之间的差别在于用于填充多边形的内部的规则方面的不同。图3表示按照称为奇偶填充规则的规则填充多边形(本实施例中为星形)的内部的例子。图4是按照称为非零填充规则的规则填充相似多边形的例子。

下面简要说明奇偶填充规则和非零填充规则。奇偶填充规则是从在某一区域(闭合回路)的内部的任意点，沿任意方向绘制半直线(射线)；按照半直线与所述区域的边缘相交处的方向，递增或递减计数器；并确定计数器读出为奇数的区域被填充，计数器读出为偶数的区域不被填充。非零填充规则是通过类似地递增或递减计数器，填充计数器读数不为零的区域。在文献“Scalable Vector Graphics(SVG)1.1Specification”，W3C Recommendation 14 January 2003中说明了上述规则的细节。该文献可从网站： www.w3.org/TR/SVG获得。

这两种规则，即奇偶填充规则和非零填充规则被描述成例证的填充规则。它们仅仅是例子，本发明并不局限于此。可以使用任意填充规则。

矢量数据组的说明

现在说明将形成待描绘图形的输入的矢量数据组，或者与之对应的点数据组。

这里说明的矢量数据组是包括两组点数据P1(n)(起点)，P2(n)(终点)的多组矢量数据，每一组具有二维(或三维)坐标，其中n＝1，...，N，N表示构成矢量数据组的矢量的数目。由一组矢量数据代表的矢量V(n)由V(n)＝P2(n)-P1(n)表示。参考符号V(n)表示由第n组矢量数据代表的矢量；P1(n)表示与形成第n个矢量的起点有关的点数据；P2(n)表示与形成第n个矢量的终点有关的点数据。在本发明中处理的矢量数据组中，相互连续的矢量共有一个终点。总之，P1(n)＝P2(n-1)的关系成立。这样获得的矢量数据组形成利用描笔的单一笔划绘制的多边形图形(参见图5)。图5表示假定实现N＝3，并且作为图形，形成一个三角形而获得的例子。

当没有达到P2(N)＝P1(1)时，形成的图形未被闭合。这种情况下，假定由P1(N+1)＝P2(N)和P2(N+1)＝P1(1)代表的第N+1个点虚拟存在，那么图形被视为闭合图形(参见图6)。在图6的情况下，图形被视为闭合的四边形，只要存在虚拟矢量点V(4)。

由矢量数据组形成的多边形可采取由普通多边形构成的任意形状，并且可采取凹陷形状或者自交形状，以及凸出形状(图7)。

可按照和矢量数据组相同的方式处理点数据组。假设点数据组被表示成P(n)，n＝1、...、N，那么下面定义的V(n)对应于矢量数据组。

V(n)＝P(n+1)-P(n)    n＝1、...、N-1    ...(1)

当点数据组被输入时，借助上述变换，该输入可作为矢量数据组被处理。

矢量数据组管理单元的说明

矢量数据组管理单元1管理如上所述作为图形描绘的输入而获得的矢量数据组。

具体地说，矢量数据组管理单元1管理作为输入获得的哪一个矢量数据组是将成为当前处理对象的一组矢量数据。

当开始处理时，矢量数据组中的第一组矢量数据被选为处理对象。在后续步骤中，矢量数据组管理单元1从后面说明的目标点管理单元4接收将变成处理对象的点数据的处理已结束的通知；顺序把将成为处理对象的矢量数据更新为第二矢量数据、第三矢量数据、...。当不再存在将变成处理对象的矢量数据时，向后面说明的描绘单元12发送处理结束的通知。

下面给出矢量数据组管理单元1的详细处理流程(图8)。首先，矢量数据组管理单元1把待处理的矢量的编号设为“1”(S101)。之后，矢量数据组管理单元1把矢量数据V(n)设为管理对象(S102)。随后，矢量数据组管理单元1把作为处理对象的矢量数据V(n)通知矢量数据提取单元2(S103)。之后，矢量数据组管理单元1等待目标点管理单元4发出的结束通知。当收到结束通知时，矢量数据组管理单元1使处理进入下一步骤(S104)。在步骤S105中，矢量数据组管理单元1确定所有各组矢量数据是否都已被处理。当不是所有各组矢量数据都已被处理时，处理进入步骤S106。当所有各组矢量数据都已被处理时，处理进入步骤S107。在步骤S106中，矢量数据组管理单元1更新处理对象的矢量号“n”。一般来说，“n”被加1，处理返回步骤S102。更新不必按照连续的方式进行。按照任意规则，预定的一组矢量数据也可被作为管理对象。在步骤S107中，矢量数据组管理单元1把处理已完成的通知发送给描绘单元12。上面是典型处理流程的细节。

在实施例中，在步骤S103，从矢量数据组管理单元1向矢量数据提取单元2通知的矢量数据V(n)用作矢量号信息。

矢量数据组管理单元1管理在后续处理操作中，将成为处理对象的矢量数据V(n)。上面的处理流程只是一个例子。利用任意选择方法选择的V(n)可被用作处理对象。

矢量数据提取单元

下面说明矢量数据提取单元2。

矢量数据提取单元2通过利用矢量数据组管理单元1通知的和处理对象有关的矢量号信息，从输入的矢量数据组获得矢量数据，包括：矢量起点P1的坐标；矢量终点P2的坐标；和指示用于填充矢量的颜色的属性信息。

在实施例中，矢量号信息用作第一管理信息，矢量数据组管理单元1根据其管理矢量数据组。

虽然例证的坐标和颜色属性被描述成矢量数据，不过本发明并不局限于此。可获得包括在作为输入而获得的矢量数据组中的所有类型或者一些类型的数据。

这样获得的矢量数据被传送给后面说明的起点-终点计算单元3。

起点-终点计算单元

下面说明起点-终点计算单元3。

起点-终点计算单元3根据从矢量数据提取单元2接收的和作为处理对象的矢量有关的数据，计算后续处理的起点和终点。

在后续操作中，说明本实施例的图形描绘操作，其中在垂直方向(Y轴的方向)被用作基准的时候进行图形描绘操作。这只是一个例子，本发明并不局限于该例子。也可在水平方向(X轴的方向)被作为基准的时候，或者在任意方向被作为基准的时候进行图形描绘操作。希望描绘的图形的主轴的方向(分散最小的方向)或类似物也可被认为是任意方向。此外，所述方向并不局限于二维方向。

起点-终点计算单元3主要计算起点的“y”坐标和终点的“y”坐标，同时把均包括在矢量数据中的两个点P1(矢量的起点)和P2(矢量的终点)中“y”坐标较小的那个点作为起点，而把“y”坐标较大的另一个点作为终点。下面给出详细的处理流程(图9)。

点P1的坐标被视为(x1，y1)，点P2的坐标被视为(x2，y2)。首先，相互比较点P1的“y”坐标和点P2的“y”坐标，从而确定这两个“y”坐标是否彼此相等(y1＝y2)(S201)。当它们彼此相等时，处理进入步骤S205。当它们彼此不相等时，处理进入步骤S202。在步骤S202中，确定关系y1＜y2是否成立。当该关系成立时，处理进入步骤S204。相反，当该关系不成立时，处理进入步骤S203。

在步骤S203中，起点的“y”坐标ys被设为y2+1，终点的“y”坐标ye被设为y1。类似地，在步骤S204中，坐标ys被设为y1，坐标ye被设为y2-1。在步骤S205中，坐标ys被设为y1，坐标ye被设为y2。

图10A至10C示意表示这些关系。当点P1的“y”坐标等于点P2的“y”坐标时(图10A)，存在两种可能，如图所示。无论如何，得到ys＝ye＝y1(＝y2)。这种情况下，起点和终点具有相同的“y”坐标。

当关系y1＜y2成立时；即，当P1的“y”坐标较小时(如图10B中所示)，P1的“y”坐标y1被视为起点，位于P2之前的点P2′的“y”坐标y2-1被视为终点。

没有简单地把P2选为终点的原因是因为P2成为下一矢量的起点，从而在下一矢量的处理时执行描绘操作的处理。如果在该步骤中，P2被包括在终点中，那么处理变成双重的。当考虑处理成本时，描绘效率被降低(图11)。在该图案中，实现P1(n+1)＝P2(n)，从而出现描绘效率的降低。

同样地，当y1＞y2成立时；即，当P1的“y”坐标较大时(如图10C中所示)，位于P2之前的点P2′的“y”坐标y2+1被视为起点，P1的“y”坐标y1被视为终点。

已举例说明了其中出于提高描绘效率的目的，计算相邻点，而不是当被计算时将被双重处理的点作为终点的“y”坐标ye的例子。但是，本发明并不局限于该例子。另一种可接受的方案是具有较大“y”坐标的点的“y”坐标被简单地计算为终点。

至此计算了起点的“y”坐标和终点的“y”坐标。起点-终点计算单元3把结果发送给后面说明的目标点管理单元4。

上面举例说明了具有较小“y”坐标的点被视为起点，具有较大“y”坐标的点被视为终点的情况。但是，本发明并不局限于此。相反，具有较大“y”坐标的点可被视为起点，具有较小“y”坐标的点可被视为终点。

另一方面，也可简单地把矢量的起点P1视为起点，把终点P2视为终点。相反，也可简单地把点P2视为起点，简单地把点P1视为终点。

也可采用除上述方法以外的方法，只要在整个矢量数据的范围内，选择起点和终点的选择方式一致，从而通过利用计算的起点和计算的终点能够唯一地执行后面描述的后续操作即可。选择“y”坐标作为基准的原因在于如上所述，该实施例是利用其中垂直方向被视为基准的例子来说明的。实施例并不局限于该例子。可按照在基准方向上产生相似优点的方式恰当地改变基准方向。

虽然上面说明了获得矢量数据的例子，不过这同样适用于其中输入点数据组的情况，如上所述(参见<矢量数据组的说明>的段落)。当输入了点数据组时，起点-终点计算单元3进行上述变换，以矢量数据的形式处理变换后的数据，从而执行类似的处理。

目标点管理单元

下面说明目标点管理单元4。

目标点管理单元4接收矢量数据提取单元2获得的并且与要处理的矢量有关的数据，以及起点-终点计算单元3计算的起点-终点数据，把矢量数据分割成点(像素)，从而以和待处理的点(像素)有关的数据的形式管理矢量数据。

具体地说，目标点管理单元4如图12中所示的处理流程指示的那样操作。首先，起点-终点计算单元3计算的起点被设为待处理的目标点(待处理的目标像素)(S301)。随后，该待处理的点(“y”坐标的值是当前目标点)被作为管理对象(S302)。把和在步骤S302中作为管理对象的点，例如“y”坐标有关的信息通知后面说明的目标点计算单元5(S303)。目标点管理单元4等待来自填充信息计算单元7的处理结束的通知，在收到该通知之后进入步骤S305。在步骤S305中，确定起点-终点计算单元3计算的终点的处理是否已结束。当终点的处理还没有结束时，处理进入步骤S306。当确定终点的处理已结束时，处理进入步骤S307。在步骤S306中，更新待管理的目标点的“y”坐标，并且处理返回步骤S302。在步骤S307中，说明目标点管理单元4已结束处理的消息被传送给矢量数据组管理单元1。

在该实施例中，目标点管理单元4充当处理顺序计算单元，用于计算矢量数据提取单元2提取的矢量数据的处理顺序。

目标点计算单元

下面说明目标点计算单元5。

目标点计算单元5接收属于借助矢量数据提取单元2获得的待处理矢量的数据，以及和目标点管理单元4通知的待管理的目标点有关的信息；并计算属于待管理目标点的坐标的数据。

根据属于包括在矢量数据提取单元2获得的矢量数据中的矢量的起点P1和终点P2的数据，以下面提供的等式(2)的形式，能够获得在两个点，即起点P1和终点P2之间延伸的部分线的方程式。

参考符号“y”必须满足min(y1，y2)≤y≤max(y1，y2)。参考符号min(a，b)表示返回“a”或“b”中坐标值较小者的函数，max(a，b)表示返回“a”或“b”中坐标值较大者的函数。

通过使用等式(2)，根据包括在目标点管理单元4通知的管理目标点信息中的待管理目标点的“y”坐标，能够计算待管理的目标点的“x”坐标。

目标点计算单元5通过把计算的待管理目标点的“x”坐标和目标点管理单元4获得的“y”坐标结合起来，确定待管理目标点的坐标(x，y)，并把坐标(x，y)发送给后面描述的目标点确定单元6。

上面说明了利用等式(2)，根据直线的方程式计算“x”坐标的方法。但是，本发明并不局限于该方法。也可利用另一种方法，比如Bresenham线算法计算“x”坐标。当使用Bresenham线算法时，前面描述的目标点管理单元4预先计算起点的初始“x”坐标。目标点计算单元5只计算差别信息，从而使计算变得更快。也可利用除上述方法以外的方法计算“x”坐标。

目标点确定单元

下面说明目标点确定单元6。

目标点确定单元6通过利用目标点计算单元5计算的待处理目标点的坐标和将成为输入的矢量数据组，确定位于目标点两侧的点(像素)是否是待填充的区域；并输出和关于所述像素的确定有关的信息，以及待处理的目标像素的坐标。

具体地说，假定待目标点计算单元5计算的目标点P的坐标为(x，y)，确定位于目标点两侧的两个点，即点Pleft(x-1，y)和点Pright(x+1，y)是否是待填充的区域。

待填充区域的确定

下面说明待填充区域的确定。待填充区域的确定用于确定目标点是否是由预定规则确定的待填充区域。在下面的说明中，在以前述非零填充规则作为填充规则的同时，说明待填充区域的确定。

图13是待填充区域的确定的流程图。

在步骤S401中，计数器的计数被重置(cnt＝0)。

在步骤S402中，待检查的矢量号被初始化(i＝0)。

在步骤S403中，获得和待检查的矢量有关的信息。通过利用矢量号“i”获得属于待检查的矢量V(i)的数据。

在步骤S404中，确定目标点是否包括在待检查的矢量V(i)中。一种确定方法是检查目标点的坐标是否包括在标记为矢量V(i)的部分线中。另一种方法也可用于所述确定。当所述坐标被包括时，目标点被确定为待填充的区域，处理进入步骤S415。当所述坐标不被包括时，处理进入步骤S405。

在步骤S405中，确定目标点是否位于待检查的矢量的上方。当目标点位于所述矢量的上方时，处理进入步骤S406。否则，处理进入步骤S408。

在步骤S406中，相对于目标点，确定待检查的矢量是否从左变到右。当矢量改变时，处理进入步骤S410。否则，处理进入步骤S407。

在步骤S407中，确定待检查的矢量是否从右变到左。当矢量改变时，处理进入步骤S411。如果否，那么处理进入步骤S412。

在步骤S408中，相对于目标点，确定待检查的矢量是否从左变到右。当矢量改变时，处理进入步骤S410。否则，处理进入步骤S409。

在步骤S409中，确定待检查的矢量是否从右变到左。当矢量改变时，处理进入步骤S411。否则，处理进入步骤S412。

在步骤S410中，计数器的计数被加1(cnt＝cnt+1)。

在步骤S411中，计数器的计数被减1(cnt＝cnt-1)。

在步骤S412中，确定是否已完成所有矢量的检查。如果没有完成检查，那么处理进入步骤S413。如果完成了检查，那么处理进入步骤S414。

在步骤S413中，待检查的矢量被更新(i＝i+1)，处理返回步骤S403。

在步骤S414中，根据计数器的计数(cnt)，进行关于填充的确定。具体地说，当计数器的计数不为零时，目标点被确定为待填充的区域。如果否，那么目标点被确定为不是待填充的区域。

在步骤S415中，通知关于目标点是否是待填充区域的确定的结果，并结束处理。

上面的说明涉及基于非零填充规则的例证填充确定处理。在该例子中，操作员想象站在目标点的位置，顺序关于每组矢量数据观看由矢量数据组形成的多边形，从而检查操作员的身体是否转动一圈。在身体转动一圈的情况下，计数器的计数取非零值，目标点被确定为待填充的区域。

上述确定方法只是一个例子，本发明并不局限于该例子。也可使用另一种确定方法，比如绘制通过目标点的直线，并检查该线条交叉矢量数据组的次数的方法等等。

虽然至此以非零填充规则为例说明了填充规则，不过填充规则并不局限于该规则。还可使用奇偶填充规则或者另一规则。当规则改变时，确定是否能够实现填充的方法也分别被改变。这种情况下，也可使用符合上述规则的方法或者另一方法。

两个点的确定结果的输出

目标点确定单元6通过利用上面所述的“待填充区域的确定”，获得关于位于目标点的两侧的点，即Pleft(x-1，y)和Pright(x+1，y)是否将被填充的确定的结果。该结果和目标点的坐标信息一起被输出。

填充信息计算单元

下面说明填充信息计算单元7。

填充信息计算单元7根据从目标点确定单元6获得的待处理的目标点的坐标，和关于位于目标点两侧的点(像素)是否将被填充的确定有关的信息，确定目标点是否是扫描线中涉及填充操作的点。当目标点涉及填充操作时，填充信息计算单元7产生该信息。

这里，扫描线被定义成包括目标点的线条；即，当目标点的坐标为(x1，y1)时，由y＝y1表述的线条。

对于每条扫描线的图形描绘

首先，将说明对于每条扫描线的图形描绘操作。对于每条扫描线的图形描绘是利用多个线条，对于每条扫描线描绘图形的填充区域，只要描绘被视为基于每条扫描线执行的操作。

例如，如图14中所示的多边形是可得到的。当设想这种图形的描绘时，通过把该图形分成将基于每条扫描线描绘的多个线条，可描绘该图形，如图15中所示。为了便于图解说明，图15被稍微放大。为了便利和例示，线条被分隔开。实际上，线条被像素精确地描绘。

考虑和图16中所示的一条扫描线对应的一部分的“y”坐标。多边形的描绘可被理解成被替换成多个线条的描绘(就图16来说，两个线条的描绘)。线条的描绘只需要用于描绘线条的起点和终点。即，只要能够获得和图16中的点P1、P2、P3和P4有关的信息，图形就可被描绘。

图16中的点P1和P3是用于描绘线条的起点，从而下面被称为线IN点。P2和P4是用于描绘线条的终点，从而下面被称为线OUT点。

当设想对于每条扫描线的图形描绘时，可认为计算线IN点和线OUT点更可取。

根据两个点的确定结果，确定目标点的线IN点和线OUT点

通过使用两个点，即点Pleft(x-1，y)和点Pright(x+1，y)是否位于目标点确定单元6确定的目标点(x，y)的两侧的确定结果，确定目标点是线IN点，线OUT点还是某一其它点。

关于两个点的确定表现为下面提供的四种可能结果：

(1)两个点都是假的；即，(空白)*(空白)

(2)左边的点是真的，而右边的点是假的；即，(填充)*(空白)

(3)左边的点是假的，而右边的点是真的；即，(空白)*(填充)

(4)两个点都是真的；即(填充)*(填的)，其中参考符号*表示关心的点(x，y)。此外，符号(空白)表示不被填充的区域，符号(填充)表示待填充的区域。

在包括目标点的每条扫描线中设想填充多边形的处理。

就(1)来说，两个点(Pleft和Pright)都是将不被填充的区域。因此，目标点*是扫描中不涉及填充操作中的点。具体地说，目标点既不是线IN点又不是线OUT点。

就(2)来说，目标点*的左侧(Pleft)是待填充的区域，目标点*的右侧(Pright)是将不被填充的区域。因此，目标点*可被认为是该线条中的待填充区域的终点；即，线OUT点。具体地说，待填充的区域始于位于目标点*的左侧的点，目标点*充当待填充区域的终点。

就(3)来说，目标点*的左侧(Pleft)是将不被填充的区域，目标点*的右侧(Pright)是待填充的区域。因此，目标点*可被认为是该线条中的待填充区域的起点；即，线IN点。具体地说，待填充的区域始于目标点*，位于目标点*右侧的任何点充当待填充区域的终点。

就(4)来说，由于位于目标点*两侧的点(Pleft和Pright)是待填充的区域，因此目标点*可被认为是包括在待填充区域中的一个点。具体地说，待填充的区域始于位于目标点*左侧的任意点，位于目标点*右侧的任意点充当待填充区域的终点。具体地说，目标点可被认为既不是线IN点又不是线OUT点。

计算的填充信息的输出

如前所述，填充信息计算单元7获得和目标点的填充有关的信息；即，目标点[坐标(x1，y1)]是(1)线IN点，(2)线OUT点，和(3)某些扫描线(其中实现y＝y1的扫描线)中的某一其它点中的任意之一。该信息被输出给后面说明的填充信息记录单元8。

填充信息记录单元

下面说明填充信息记录单元8。

填充信息记录单元8把填充信息计算单元7获得的和待处理的目标点有关的填充信息记录到填充信息存储区9中。

填充信息存储区的说明

填充信息存储区9是用于保留填充信息的任意存储单元。例如，填充信息存储区9形成于包含在实现本实施例的设备中的内部存储器中。

但是，填充信息存储区9并不局限于内部存储器。可以使用任意装置，只要该装置能够保留填充信息。此外，填充信息存储区9并不局限于实现本实施例的设备内的某一位置，也可以可拆卸的存储装置(USB存储设备，SD存储卡等)、磁性存储介质(CD-R、DVD-R等)、通过任意通信装置(有线LAN、无线LAN、比如WCDMA之类利用便携式电话机的通信等)连接的存储装置(NAS装置，包含在另一设备中的HDD等)等等。

将记录在填充信息存储区9中的填充信息一般是目标点的坐标对应于(1)线IN点、(2)线OUT点和(3)某一其它点中的任意一个。但是，填充信息并不局限于此，也可记录至少包括上述信息的任意信息。

用于填充信息存储区9的各种存储方法都是可想得到的。虽然下面将说明方法之一，不过该方法只是一个例子，本发明并不局限于该方法。

图17表示用于填充信息存储区9的一个例证存储方法。图17中所示的方法表示其中为每条扫描线准备能够保存两个点，即线IN点和线OUT点的一个栈(可变区域)，并准备所有扫描线(1080线)的栈的例子。

所有扫描线的栈表示希望最终被描绘的区域中的扫描线的总数。例如，就全HDTV的描绘区域来说，实现1920×1080分辨率。因此，准备1080条线的栈。

在每个栈中，保存被确定为线IN点的点的“x”坐标和被确定为线OUT点的点的“x”坐标。在图17中，xi##(n)表示保存的被确定扫描线##的线IN点的点的“x”坐标，xo##(n)表示保存的被确定为扫描线##的线OUT点的点的“x”坐标。

填充信息记录单元的操作

例如，当从填充信息计算单元7收到指示被赋予扫描线号1078的目标点[目标点坐标为(xs，1078)的点]是线IN点时，填充信息记录单元8把该信息记录到填充信息存储区9中。在图17中所示的情况下，一直到xi1078(n)的n+1条信息项已被记录在被赋予扫描线号1078的线IN点的栈中；从而，xs(它是目标点的“x”坐标)的值作为第n+2条信息项被记录在记录信息的尾部。

虽然上面举例说明了例证的记录方法，不过记录方法并不限于该例子。该例子只是一个实施例，也可采用除上述例证记录方法以外的记录方法。虽然说明了其中目标值的“x”坐标被增加到记录信息的尾部的例子，目标点的“x”坐标也可被增加到记录信息的头部，或者按照任意条件(例如，按照坐标的升序)被记录在任意位置。

描绘区域计算单元

下面将说明描绘区域计算单元10。

描绘区域计算单元10根据从矢量数据提取单元2获得的与待处理目标矢量相关的数据，计算和图形将被描绘的区域有关的信息。

例如，当显示描绘图形的屏幕的范围采取1920×1080分辨率时，作为描绘区域，需要1920×1080的最大区域。但是，通常情况下，多边形实际存在的区域是1920×1080区域中的局部区域。例如，在图18中所示的情况下，图形只存在于1920×1080区域的中心。这种情况下，如图19中所示，由于图形只存在于包含该图形的最小矩形区域[从坐标(x0，y0)延伸出的高度为“h”、宽度为“w”的区域]中，因此基本要求是只把该矩形区域定义为图形将被描绘的区域。从而，与整个屏幕被视为描绘区的情况相比，描绘区可被限制，预期能够提高描绘速度。

出于这种目的提供描绘区域计算单元10；描绘区域计算单元10计算和最小矩形区域有关的信息，所述信息包括与由矢量数据提取单元2提取的待处理目标矢量相关的数据，并根据这样计算的最小矩形区域更新图形描绘区域信息。

如上结合该实施例所述，当垂直方向(“y”轴方向)被作为基准时，在“y”轴方向上基于每条扫描线进行图形描绘操作。因此，在和包括在图形中的最小矩形有关的各条信息中，只有和“y”轴方向上的最小矩形有关的数据才是重要的。即，只有“y”轴方向上的矩形区域的下限(图19中的y0)和“y”轴方向上的矩形区域的上限(图19中的y0+h)才是重要的。描绘区域计算单元10计算所述下限(下面称为y_min)和所述上限(下面称为y_max)(图20)。

图21表示计算流程图。在步骤S501中，设置y_min的初始值和y_max的初始值。在步骤S502中，获得矢量数据提取单元2提取的矢量数据。随后，在步骤S503中，矢量的起点的“y”坐标被设为y0。在步骤S504中，确定关系y_min＞y0是否成立。当该关系成立时，处理进入步骤S505。在步骤S505中，y_min被设为y0的值，处理进入步骤S506。相反，当该关系不成立时，处理直接进入步骤S506。同样地，在步骤S506中，确定关系y_max＜y0是否成立。当该关系成立时，在步骤S507中把y_max设成y0，处理进入步骤S508。相反，当该关系不成立时，处理直接进入步骤S508。在步骤S508中，确定是否已完成关于所有矢量的处理。当未完成关于所有矢量的处理时，处理返回步骤S502。当已完成关于所有矢量的处理时，处理结束。从而，能够获得y_min的值和y_max的值。

上面的说明仅仅是一个实施例，本发明并不局限于该实施例。也可利用另一种方法计算待描绘图形的“y”坐标的上限和下限。

在上面的说明中，只计算“y”坐标。但是，本发明并不局限于该实施例。借助类似的手段可计算关于“x”坐标的信息，并且关于“x”坐标的信息可和“y”坐标一起被输出。当输出为所述上限和下限时，可以采用任意格式的表达，例如区域的下限和高度，而不是关于“x”坐标的信息，只要在信息量方面，所述格式与所述上限和下限相同。

描绘区域修正单元

下面说明描绘区域修正单元11。

描绘区域修正单元11用于修正描绘区域计算单元10计算的描绘区域信息。由将成为输入的矢量数据组形成的整个图形不一定落在描绘区域内。

图22表示了这种例子。图22表示一部分图形落在描绘区域之外的例子。这种情况下，得到y_min＜0，该部分图形不被描绘。此时，该关系必须被修正为y_min＝0。描绘区域修正单元11进行这样的修正。

具体地说，当y_min＜0时，假定实现y_min＝0。在y_max＞＝已实现描绘区域的“y”坐标的上限(图22中所示例子中的1080)的关系的情况下，进行修正，使得获得描绘区域的“y”坐标的上限＝y_max的关系。

描绘数据修正单元

下面说明描绘数据修正单元12。

当从矢量数据组管理单元1收到矢量数据组的处理已完成的通知时，描绘数据修正单元12读取保存在填充信息存储区9中的供描绘之用的信息，并进行修正，使得该信息变成适合于后面说明的描绘单元13所进行的描绘的数据。

如图17中所示，当从矢量数据组管理单元1收到矢量数据组的处理已完成的通知时，关于包括在形成希望描绘的图形的所有矢量中的点(像素)，获得与线IN点和线OUT点有关的填充信息

但是，当使用关于填充信息记录单元8说明的方法时，按照矢量的处理顺序，从栈的头部开始堆叠矢量。于是，矢量的出现顺序发生变化。当考虑到描绘线条而引起的成本，这会导致效率降低。

当想要描绘的图形的一部分落在描绘区之外时，会出现线IN点或者线OUT点落在描绘区之外的情况(图23)。这种情况下，从线IN点到描绘区的左端的线条的描绘并不反映在实际描绘区上，从而是无用的。这导致图形描绘设备的速度的降低。

当图形的形状复杂时，存在多个矢量经过相同的线IN点和线OUT点的情况，从而在数据方面会出现重叠。这种情况下，多次描绘同一线条是浪费的。直线(每条直线均用由一个线IN点和一个线OUT点组成的一对点表达)的区域通常相互交叉。这种情况下，多条直线可被集中成单一直线。从而，能够减少直线被描绘的次数，这又会导致速度加快。

描绘数据修正单元12解决这些问题并且执行下述操作：

1.按照升降(或者降序)对线IN点和线OUT点分类。

2.把落在描绘区之外的数据修正为描绘区的边缘。具体地说，当线IN点的“x”坐标和线OUT点的“x”坐标取负值时，“x”坐标被修正为零。当超过描绘区的宽度时，“x”坐标被修正为描绘区的宽度。最好，当落在描绘区的范围之外时，对应的线IN点和对应的线OUT点均作为不必要的数据从栈中删除。

3.删除和冗余的线IN点冗余的线OUT点有关的数据。具体地说，当与线IN点和线OUT点有关的数据中存在重叠时，删除所述重叠。最好，当存在形成多条直线的数据，并且所述多条直线将被包括在以和由一个线IN点和一个线OUT点组成的一对点有关的数据形成的一条直线中时，删除形成所述将被包括的多条直线的数据。

对于修正后的数据来说，在相对于栈的头部位于相同位置的的线IN点和线OUT点被用作对应点的时候，仅仅描绘直线(线条)。从而，目标扫描线中形成落在描绘范围外的希望描绘的一部分图形的区域从屏幕的左侧被顺序描绘。

描绘单元

下面说明描绘单元13。

描绘单元13通过基于每条扫描线扫描直线(线条)，描绘从描绘数据修正单元12获得的描绘数据。此时，通过使用从描绘区域修正单元11获得的和描绘范围有关的信息(具体地说，描绘开始扫描线和描绘终止扫描线)，限制描绘操作的范围，从而加快描绘操作的速度。

图24表示描绘单元13的处理流程图。

与扫描线号“m”相关的第n个线IN数据被作为line_in(m，n)，并且线OUT数据被作为line_out(m，n)。包括在扫描线号“m”中的数据的元素的数目被作为n_element。此外，从描绘区域修正单元11获得的描绘开始扫描线号被设成m0，终止扫描线号被设为m1。

首先，在步骤S601中，m0被设成分配给作为描绘目标的扫描线的编号。随后，在步骤S602中，分配给待处理的目标数据的编号“n″被初始化，并计算元素的数目n_elmt。随后在步骤S603中，获得L0＝line_in(m，n)，L1＝line_out(m，n)的值。在步骤S604中，由L0、L1形成的线条(直线)被实际描绘。从而，以L0、L1为其两端的直线被描绘。在步骤S605中，确定是否已完成所有元素的描绘。当还没有完成所有元素的描绘时，在步骤S606中，描绘点被更新(为n＝n+1)，处理返回步骤S603。当已完成所有元素的描绘时，处理进入步骤S607。在步骤S607中，确定是否已完成一直到扫描线m1的扫描线的描绘。当描绘操作还没有完成时，描绘扫描线被更新(为m＝m+1)，处理返回步骤S602。当已完成一直到扫描线m1的扫描线的描绘时，结束处理。

专门为描绘线条而设计的HW(硬件)可被用于实际描绘线条，或者也可采用通用图形描绘LSI(GPU；图形处理单元)等。另一方面，通过利用另一手段，也可以软件的方式执行线条的实际描绘。

如上所述，基于每条扫描线连续进行描绘，如图15中所示。最后，完成如图14中所示的多边形图形的描绘。

上面说明的方法只是该实施例的一种模式，方法并不局限于这种方法。

本实施例的优点

按照本发明的实施例，描绘操作不会与由多组输入矢量数据形成的图形的复杂度相关联地被复杂化。例如，就利用三角形化的描绘方法(参见非专利文献2)来说，当在输入图形中存在复杂的自相交时，必须把输入图形分成一组由单一闭合回路形成的简单多边形。为此，取决于图形的复杂性，次数极多地应用分割操作，这使后续的处理操作复杂。这是故障(程序错误)的一个主要因素。当输入图形变得非常复杂时，可能存在意外形状的输入。此时，上述分割操作不能很好地起作用。即，可认为造成处理量正比于图形的复杂性而增大的方法缺乏稳定性。同时，根据本发明的实施例，基于每个矢量数据进行处理。处理细节并不取决于图形的形状。于是，处理量不会正比于图形的复杂性而增大。于是，可认为本发明的实施例的方法是稳定的。

按照本发明的实施例的方法，唯一的要求是在进行描绘操作之前，保存与线IN点和线OUT点有关的多组数据。这只需要很少量的数据，使用的存储量较小。同时，在描绘操作之前，三角形化方法需要各种预处理操作(细节参见相关技术文献2)。于是，必须保存大量的中间数据。描绘操作也是基于每个三角形进行的，从而使用的存储量大于本发明实施例的基于每个线条进行描绘的方法所需的存储量。(在相关技术文献3中说明的)利用模板缓存的方法需要称为模板缓存的特殊存储区来执行描绘操作。模板缓存主要需要和描绘区域相等的区域。此外，描绘操作本身是基于每个屏幕进行的，从而必须使用极大的存储容量。从使用的存储容量的观点来看，本发明的实施例中描述的方法大大优于上面提及的相关技术方法。

结合该实施例说明的方法只要求准备描绘操作时，能够描绘线条的设备。于是，不需要复杂的定制设计的电路，通过使用简单电路或者通用图形LSI能够具体体现本发明。从这个观点来看，产生和可用资源有关的重大优点。

通过采用上面提及的结构，结合本发明的实施例说明的方法能够以比基于点的方法和相关技术的基于扫描线的方法更高的速度进行图形描绘。

根据上面的描述，按照本发明的实施例的方法，可提供一种图形描绘设备和图形描绘方法，所述设备和方法解决相关技术方法中的缺点，比如在资源数量较少的情况下方法难以使用，缺乏稳定性，速度不高，并且在只有少量资源或者少量存储器可用的情况下，所述设备和方法能够实现高速并且稳定的操作。

实施例的第一改进

图25表示按照本发明的实施例的第一改进的图形描绘设备的总体方框图。通过向实施例中增加矢量数据组修正单元14，体现本发明的实施例的第一改进。

矢量数据组修正单元

下面说明矢量数据组修正单元14。矢量数据组修正单元14用于修正输入的矢量数据组。

当与零矢量相关的数据被包括在矢量数据组中时，该数据可被排除。

当两个或者更多的连续矢量沿相同方向排成一行时；即，下述关系成立时，这些矢量可被合并成单一矢量。

V(n)/|V(n)|＝V(n+1)/|V(n+1)|＝…＝V(n+m)/|V(n+m)|

其中m＝1，2，...

具体地说，在上述关系中，V(n)的终点被V(n+m)的终点代替，并且与V(n1)，...，V(n+m)相关的数据可被删除。

即使当连接矢量沿相反方向排成一行时，矢量也可按照相同方式被合并。计算连续矢量合并成的矢量的两个端点，并用该新的矢量代替V(n)。被合并的其它矢量可被删除。

矢量数据组修正单元14对具有冗余表达的矢量数据组进行修正。通过所述修正，矢量数据组的总数可被减少，这又导致后续处理的速度的提高。

至此说明了例证的冗余表达。但是，冗余表达并不局限于上述冗余表达。可以使用能够减少矢量数据组的总数，而不涉及对由矢量数据组形成的多边形图形的形状的修改的所有改进。

在本发明中的实施例的第一改进的后续处理方面，根据需要，用说明由矢量数据组修正单元14修正的矢量数据组的描述替换实施例中的说明作为输入的矢量数据组的描述。

除上述操作以外的其它操作和第一实施例中的操作相同。

实施例的第二改进

图26表示按照本发明的实施例的第二改进的图形描绘设备的总体方框图。

通过增加新的描绘数据修正单元15来代替实施例的图形描绘设备的描绘数据修正单元12，体现本发明的实施例的第二改进，其中通过利用保存在填充信息存储区9中的数据，连续修正填充信息记录单元8获得的记录信息，更新填充信息存储区9中的数据。与实施例的图形描绘设备的描绘数据修正单元12连接的各个部分直接与描绘单元13连接。

描绘数据修正单元15的操作基本上与实施例的图形描绘设备中的描绘数据修正单元12的操作相同。描绘数据修正单元12和15之间的区别在于实施例的图形描绘设备的描绘数据修正单元12修正保存在填充信息存储区9中的数据，而描绘数据修正单元15累积填充信息记录单元8获得的记录信息，同时修正所述记录信息；把记录数据保存在填充信息存储区9中，同时连续修正记录数据(同时，累积在填充信息存储区9中的数据也被更新)。

当从矢量数据组管理单元收到矢量数据组的处理已完成的通知时，描绘单元13开始处理。除此之外，描绘单元13完全与实施例的对应物相同。

实施例的第三改进

图27表示按照本发明的实施例的第三改进的图形描绘设备的总体方框图。

第三改进和实施例之间的区别在于描绘数据修正单元12只与描绘单元13连接，而不是被置于填充信息存储区9和描绘单元13之间。

这种情况下，作为每条扫描线的处理之前的预处理，描绘数据修正单元12被调用。描绘数据修正单元12修正和目标扫描线有关的数据。描绘单元13再次接收修正结果，继续进行处理。具体地说，最好在图24的步骤S603的处理之前进行上述处理操作。描绘数据修正单元12执行的修正方法完全与实施例的说明相同。

第三改进与实施例的区别在于在实施例中采用顺序处理，比如“所有各组数据的修正”→“所有各组数据的描绘”，而在第三改进中，对于每条扫描线重复操作“数据的修正”→“描绘”。

实施例的第四改进

图28表示按照本发明的实施例的第四改进的图形描绘设备的总体方框图。

在填充信息计算单元7和填充信息记录单元8之间新增加一个填充信息修正单元16，填充信息计算单元7和填充信息记录单元8都示于图1中，并且与实施例相关。

填充信息修正单元16修正和填充信息计算单元7获得的待处理目标点有关的填充信息，并把这样修正的填充信息传给填充信息记录单元8。

具体地说，填充信息修正单元16修正线IN点的位置和线OUT点的位置。例如，假定相对于某一矢量获得如图29中所示的线OUT点。这种情况下，可以想到多种填充方法，比如图30中所示的把扫描线的一直到其线OUT点的扫描线的区域作为待填充图形的区域的方法，和图31中所示的把一直到位于扫描线(n-1)的线OUT点之前的点的区域作为待填充区域的另一方法。

填充方法按照当描绘多边形图形时，描绘多边形的边缘的规则而变化。按照这种描绘规则，填充信息修正单元16修正作为待处理的目标点并且由填充信息计算单元7获得的线IN点的坐标和线OUT点的坐标。

修正方法根据修正规则而变化。但是，就图30中所示的例子来说，通过使用与上扫描线和下扫描线有关的信息，计算坐标。依据矢量的方向确定使用上扫描线和下扫描线中的哪一个。

填充信息修正单元16把与线IN点和线OUT点有关的修正数据传给填充信息记录单元8。填充信息记录单元8按照结合实施例说明的相同方式不断进行处理。

虽然说明了例证的修正方法，不过本发明并不局限于这些方法。通过使用符合描绘规则的任意修正方法进行处理。根据需要，实施例及其改进可被组合实现。

与本发明的实施例相关的处理被实现成可由计算机执行的程序，所述程序还可被体现成计算机可读存储介质。

本发明的存储介质采用任何存储格式，比如磁盘、软(floppy，注册商标)盘、硬盘驱动器、光盘(CD-ROM、CD-R、DVD等)、磁光盘(MO等)、半导体存储器等，只要存储介质能够保存程序，并且可被计算机或者内置系统读取。

按照来自从存储介质的安装到计算机或内置系统中的程序的命令，在计算机上运行的OS(操作系统)；或者诸如数据库管理软件、网络之类的MW(中间件)可执行实施例的处理操作的各个部分。

本发明的存储介质并不局限于与计算机或内置系统独立的介质，而是包括保存或临时保存通过LAN、因特网等传送和下载的程序的存储介质。

存储介质的数目并不限于为1。即使实施例的处理由多个介质执行，存储介质也落在本发明的存储介质的范围之内，存储介质可采用任意构造。

本发明的计算机或内置系统按照保存在存储介质中的程序，执行实施例的各种处理操作；并且可以是任何构造，比如由个人计算机、微计算机等任意之一形成的设备，或者其中借助网络连接多个设备的系统等等。

本发明的计算机并不局限于个人计算机，而是包括内置到信息设备中的计算装置、微计算机等。能够借助程序实现本发明的设备和装置被统称为计算机。

本发明并不局限于实施例，在本发明的范围内，在实施阶段可以有各种各样的形式。此外，上面的实施例包含不同阶段的发明。通过恰当地组合多个组成元件，能够得到各种发明。例如，即使从在实施例中描述的所有组成元件中除去一些组成元件，也能够解决关于本发明要解决的问题说明的(至少一个)问题。当产生关于本发明的优点说明的(至少一个)优点时，从中除去一些组成元件的构造可被提出作为本发明。

如上关于实施例详细所述，提供一种存储空间消耗量低，高速、稳定地描绘多边形图形的设备和方法。

Claims (10)

1、一种图形描绘设备，包括：

矢量数据组管理单元，用于根据第一管理信息，管理包括各组矢量数据的矢量数据组；

矢量数据提取单元，用于根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；

处理顺序计算单元，用于计算矢量数据提取单元提取的目标矢量的处理顺序；

目标点管理单元，通过根据处理顺序确定待处理的目标点，产生用于管理目标点的第二管理信息，并通知矢量数据组管理单元目标矢量的处理已结束；

填充信息计算单元，用于根据第二管理信息确定目标点是否将被填充，和计算指示填充目标点的确定结果的填充信息；和

描绘单元，通过使用填充信息描绘多边形。

2、按照权利要求1所述的设备，还包括：

填充信息存储单元，用于保存填充信息；

填充信息记录单元，用于把填充信息计算单元计算的填充信息记录到填充信息存储单元中；和

描绘区域计算单元，用于通过根据矢量数据提取单元提取的矢量数据确定多边形将被描绘的描绘区域，计算描绘区域信息，

其中描绘单元通过使用描绘区域计算单元计算的描绘区域信息和保存在填充信息存储单元中的填充信息，描绘多边形。

3、按照权利要求1所述的设备，其中目标点管理单元通过使用从填充信息计算单元获得的指示目标的处理已结束的通知，确定待处理的目标点。

4、一种图形描绘设备，包括：

矢量数据组管理单元，用于根据第一管理信息，管理包括各组矢量数据的矢量数据组；

矢量数据提取单元，用于根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；

起点-终点计算单元，用于根据矢量数据提取单元提取的矢量数据，计算指示处理的起点和终点的起点-终点信息；

目标点管理单元，通过根据起点-终点信息确定待处理的目标点，产生用于管理目标点的第二管理信息，并通知矢量数据组管理单元目标矢量的处理已结束；

目标点计算单元，用于根据第二管理信息计算待处理目标点的像素的坐标；

目标点确定单元，用于确定是否将填充位于待处理目标点的坐标两侧的像素；

填充信息计算单元，用于根据填充信息确定单元的确定结果，计算关于目标点的填充信息；

填充信息存储单元，用于保存填充信息；

填充信息记录单元，用于把填充信息计算单元计算的填充信息记录到填充信息存储单元中；

描绘区域计算单元，用于根据矢量数据提取单元提取的矢量数据，计算和更新将描绘多边形的描绘区域；

描绘区域修正单元，通过对描绘区域计算单元计算的描绘区域进行修正，产生描绘区域信息；

描绘数据修正单元，通过对保存在填充信息存储单元中的填充信息进行修正，产生对描绘来说最佳的数据；和

描绘单元，通过使用描绘区域信息和描绘数据修正单元产生的数据，描绘多边形。

5、按照权利要求4所述的设备，还包括矢量数据组修正单元，用于对包括在矢量数据组管理单元管理的矢量数据组中的矢量数据进行修正，从而删除和合并包括在矢量数据组中的冗余矢量数据。

6、按照权利要求4所述的设备，其中描绘数据修正单元根据产生的对描绘来说最佳的数据，更新保存在填充信息存储单元中的填充信息，

其中描绘单元通过使用描绘区域信息和保存在填充信息存储单元中的填充信息，描绘多边形。

7、按照权利要求4所述的设备，其中描绘单元通过使用描绘区域信息和保存在填充信息存储单元中的填充信息，描绘多边形，

其中在与描绘单元合作地工作时，描绘数据修正单元对从描绘单元获得的描绘数据进行修正，并把修正后的描绘数据返还描绘单元。

8、按照权利要求4所述的设备，还包括填充信息修正单元，用于根据预定的渲染规则，修正填充信息计算单元计算的填充信息，

其中填充信息记录单元把填充信息修正单元修正的填充信息记录到填充信息存储单元中。

9、按照权利要求4所述的设备，其中目标点管理单元通过使用从填充信息计算单元获得的指示目标的处理已结束的通知，确定待处理的目标点。

10、一种图形描绘方法，包括：

管理包括在矢量数据组中的多组矢量数据的处理顺序；

根据第一管理信息，从矢量数据组提取作为待处理目标矢量的矢量数据；

计算提取的矢量数据的处理顺序；

根据第二管理信息和计算的处理顺序，管理待处理的目标点；

通知目标矢量的处理的结束；

根据第二管理信息确定目标点是否将被填充；

计算指示该确定结果的填充信息；和

使用计算的填充信息描绘多边形。

Images