CN106651993A - 一种在fpga中填充非自相交多边形的填充方法 - Google Patents

Abstract

本发明公开了一种在FPGA中填充非自相交多边形的填充方法，所述填充方法包括坐标获取、交点计算、交点排序及边排序、组合填充、条件判断。与现有的算法相比，本发明的方法填充过程简单，填充速度快。尤其本发明的填充方法中有关排序的处理算法，视交点个数变化的情况采用简化的排序方法，大大降低填充过程中中交点的排序运算量，极大地提高了填充速度。

Description

一种在FPGA中填充非自相交多边形的填充方法

技术领域

本发明涉及FPGA数据处理技术领域，具体来说是一种用于光刻机矢量数据栅格化的快速填充的算法。

背景技术

激光直接成像技术(laser direct imaging，简称LDI)也称为激光直写，是近年来发展起来的一种用于半导体器件生产的技术。传统的曝光工序是通过汞灯照射菲林将图像转移至基底上，而LDI则是用激光扫描的方法通过图形发生器直接将图像在基底上成像。相比较传统的曝光技术，LDI曝光过程不需要菲林，有效降低了成本，且工序简单、图像精度高，可适应更精细的图形曝光，也有利于提升生产的良率。

通常半导体器件设计的图形数据为矢量数据，包括GDS II、Gerber、ODB++等格式数据，而激光直写中图形发生器需要的数据为bitmap格式的数据，因此，需要将矢量数量栅格化处理，变成bitmap数据。栅格化数据的处理速度直接影响光刻机的产能，为了提高光刻机的产能，则需要提高栅格化的速度。

矢量图的栅格化处理一般分为3个步骤：求扫描线与多边形各个边的交点；对交点进行排序；将排序之后的点进行组合填充。传统的栅格化处理方法是由LDI系统中的主机进行图形资料解析后，将图形资料转化为利于下位机处理的图形坐标点程序，然后传输给现场可编程门阵列(FPGA)来处理还原成待曝光的bitmap数据。其中，FPGA的处理主要涉及排序和填充两个步骤。这两个步骤中，排序是最消耗逻辑资源和时间的，排序的快慢直接影响矢量图的填充速度及所使用的FPGA的价格。而对于非自相交多边形填充，最大的难度就是扫描线与多边形交点的计算与排序，如何简化排序过程是填充方法的关键因素之一。

现行的基于FPGA的填充算法仅能实现三角形和四边形的填充，而对于非自相交多边形填充，为了简化FPGA填充的难度，多数方案选择是由计算机对多边形进行三角化或直角梯形化，大大增加了计算机的处理难度和计算量。存在一种进步的算法可以实现对凸多边形进行填充。但在实际环境中，多边形多数是非自相交凹多边形。因此开发基于FPGA对非自交任意多边形的填充算法，不仅可以简化计算的处理，也可以充分利用FPGA的计算效率，大大提升生产效率。

发明内容

本发明的目的就是针对现有FPGA填充算法中排序复杂、资源消耗大和排序时间长的不足，以及现有基于FPGA的填充算法无法直接填充凹多边形的不足，提供一种快速的在FPGA中填充任意非自相交多边形的方法。

本发明仅针对非自相交多边形，即除多边形的顶点外，多边形的各边无其他交点。本发明的技术方案如下：

一种在FPGA中填充非自相交多边形的填充方法，包括如下步骤：

(1)坐标获取步骤，获取多边形各顶点的Y坐标值，得出各顶点的Y坐标值的最大值点Ymax、最小值点Ymin以及非极值点，并对多边形各边进行编号。

(2)交点计算步骤，获取Y=Ymin的直线与多边形各边的交点的X坐标值并记录交点个数以及交点所在边的编号。

(3)交点排序及边排序步骤，对交点的X坐标值进行排序，然后按照X值由小到大的顺序对交点进行交点排序，并对交点所在边依据交点排序的顺序进行边排序，记录边排序后各个边编号的顺序。

(4)组合填充步骤，对排序后的交点从x值最小的交点开始每两个组合为一组，每个交点不重复参加组合，同一组的两个交点之间进行填充，其余位置不填充。

(5)条件判断步骤，令Y=Y+1，判断Y是否大于Ymax。

若Y>Ymax时结束填充过程。

若Y不大于Ymax，则返回并执行交点计算步骤，然后进行极值点判断：

若交点中不存在非极值点的顶点或交点中存在非极值点的顶点但该顶点拥有的两条边均在当前Y直线的同一侧时，则执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程；

若交点中存在非极值点的顶点且该顶点拥有的两条边在当前Y直线的两侧时，则进行交点合并及边替换，然后执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程。

其中，当Y>Ymin且Y≤Ymax时，所述交点排序及边排序步骤存在简化算法，所述简化算法首先对当前Y直线与多边形的交点个数与上一次记录的交点个数进行比较，然后根据交点个数变化的情况执行相应简化算法：

当交点个数与上一次记录的交点个数相同，且上一次记录的交点不存在极值点的顶点，则交点对应的边顺序就是本次交点排序的顺序；

当交点个数与上一次记录的交点个数相同，且上一次记录的交点存在极值点的顶点，则对极值点的顶点具有的两条边按照对应交点的排序顺序进行排序，然后将所述两条边排序的结果作为整体参与边排序。更优选的方法是：若所述两条边排序的结果保持与上一次记录的边排序结果中此两条边的排序顺序一致时，则无需进行边排序，上一次记录的边排序结果即为本次的边排序结果；若排序结果不一致，只需要将上一次记录的边排序结果中此两条边的排序顺序交换，即是本次的边排序结果。

当交点个数比上一次记录的交点个数多时，对交点进行排序，以交点排序的结果作为交点所在的边的排序结果，将此交点所在的边的排序结果作为整体参与边排序；

当交点个数比上一次记录的交点个数少时，将减少的交点对应的边从边排序的序列中删除，剩余的边排序的序列保持不变，边排序的结果是对应交点的排序顺序。

其中，所述交点合并的方法是：将非极值点的顶点对应的两个交点合并为一个，然后进行交点排序。

其中，所述边替换的方法是：使用非极值点的顶点拥有的两条边中在当前Y直线未填充一侧的边替换当前Y直线已填充一侧的边参与边排序。

以上填充方法适用于任意边数的非自相交多边形。

本发明具有如下有益效果：

本发明涉及一种在FPGA中填充非自相交多边形的填充方法，与现有的算法相比，本发明的方法填充过程简单，填充速度快。尤其本发明的填充方法中有关排序的处理算法，视交点个数变化的情况采用简化的排序方法，大大降低填充过程中中交点的排序运算量，极大地提高了填充速度。此外，本发明的方法不仅适应于在FPGA中填充，也适用于在CPU中填充，可以有效降低CPU的时间成本。

附图说明

图1是本发明的在FPGA中填充非自相交多边形的填充方法的流程图；

图2是本发明实施例1的填充过程若干Y直线与多边形交点的示意图；

图3是本发明实施例1的填充过程的组合填充示意图。

具体实施方式

下面将结合具体实施例和附图对本发明的技术方案进行清楚完整地描述。

本发明提供一种在FPGA中填充非自相交多边形的填充方法，如附图1所示，本发明的填充方法，包括如下步骤：

(1)坐标获取步骤：获取多边形各顶点的Y坐标值，得出各顶点的Y坐标值的最大值点Ymax、最小值点Ymin以及非极值点，并对多边形各边进行编号。

(2)交点计算步骤：获取Y=Ymin的直线与多边形各边的交点的X坐标值并记录交点个数以及交点所在边的编号。

(3)交点排序及边排序步骤：对交点的X坐标值进行排序，然后按照X值由小到大的顺序对交点进行交点排序，并对交点所在边依据交点排序的顺序进行边排序，记录边排序后各个边编号的顺序。

(4)组合填充步骤：对排序后的交点从x值最小的交点开始每两个组合为一组，每个交点不重复参加组合，同一组的两个交点之间进行填充，其余位置不填充。

(5)条件判断步骤：令Y=Y+1，判断Y是否大于Ymax。

若Y>Ymax时结束填充过程。

若Y不大于Ymax，则返回并执行交点计算步骤，然后进行极值点判断：

若交点中不存在非极值点的顶点或交点中存在非极值点的顶点但该顶点拥有的两条边均在当前Y直线的同一侧时，则执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程；

若交点中存在非极值点的顶点且该顶点拥有的两条边在当前Y直线的两侧时，则进行交点合并及边替换，然后执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程。

以下是本发明的具体实施例。

实施例1

附图2(a)是本实施例待填充的多边形ABCDEFG，对此多边形的填充方法过程如下：

(1)坐标获取。获取多边形ABCDEFG各顶点Y坐标值的最大值、最小值和非极值点，如图2(a)所示，A点为极小值点，即；F点为极大值点，即。B、C、D、E、G点为非极值点。对多边形ABCDEFG各边编号，记为AB、BC、CD、DE、EF、FG、GA。

(2)交点计算。计算的直线与多边形ABCDEFG的交点，如图2(b)所示，交点分别是和，交点个数为2，交点所在的边分别是AG和AB。

(3)交点排序及边排序。比较和值的大小，，因此交点排序任意；边的排序为AG、AB、BC、CD、DE、EF、FG或AB、AG、BC、CD、DE、EF、FG。

(4)组合填充。对排序后的交点从X值最小的交点开始每两个组合为一组，每个交点不重复参加组合，同一组的两个交点之间进行填充，其余位置不填充。如图3(a)所示，即对和之间进行填充。

(5)进行条件判断。令，如图2(c)直线，判断得知，则返回交点计算步骤，计算直线与多边形ABCDEFG的交点，交点分别是和，交点个数为2，交点所在的边分别是AG和AB。交点中无非极值点的顶点，因此直接进行交点排序及边排序。

(6)交点排序及边排序(简化算法)。由于满足且，因此可使用交点排序及边排序的简化算法。通过对当前Y直线与多边形的交点个数与上一次记录的交点个数进行比较，交点个数保持不变，且上一次记录的交点存在极值点的顶点，选用方案二，对上一次极值点的顶点具有的两条边AG和AB按直线与交点的X坐标值从小到大排序排序。

首先对两个交点和排序，，则AG和AB的排序顺序为AG、AB。

如果上次边排序的结果为AG、AB、BC、CD、DE、EF、FG，则此次AG和AB的排序顺序保持与上一次记录的边排序结果中AG和AB的排序顺序一致时，上一次记录的边排序结果即为本次的边排序结果，即AG、AB、BC、CD、DE、EF、FG。

如果上次边排序的结果为AB、AG、BC、CD、DE、EF、FG，则此次AG和AB的排序顺序保持与上一次记录的边排序结果中AG和AB的排序顺序不一致，因此将上一次记录的边排序结果中AG和AB的排序顺序交换即是本次的边排序结果，即AG、AB、BC、CD、DE、EF、FG。

边排序的结果作为交点排序的结果，即。

(7)组合填充。如图3(b)所示，对和之间进行填充。

(8)进行条件判断。令，，判断新的Y直线与的关系，只要，则返回进行交点计算步骤，然后循环进行步骤(6)和(7)，直至时结束填充过程。

以下对于填充过程中一些特殊的Y直线位置进行进一步地阐述。

当时，如图2(d)所示，Y直线与多边形ABCDEFG的交点个数发生了变化，变为了4个，而的直线与多边形的个数是两个。计算直线与多边形ABCDEFG的交点，交点分别是、、、，交点所在的边对应是AG、AB、BC、CD。对交点、、、按X值从小到大进行排序，,对应的边的排序是AG、AB、BC、CD，将其作为整体参与边排序，边排序结果是AG、AB、BC、CD、DE、EF、FG。

组合填充时将和之间和和之间进行填充，和之间则不填充，填充示意图如图3(c)所示。

如图2(e)所示，当时，直线与多边形ABCDEFG的交点中出现了非极值点的顶点G，且该顶点G拥有的两条边AG和GF在当前Y直线的两侧，因此进行交点合并及边替换。

交点合并的方法是：将非极值点的顶点G对应的两个交点和合并为一个，然后进行交点排序，交点排序的结果是、、、、、。

边替换的方法是：使用非极值点的顶点G拥有的两条边AG和GF中在当前Y直线未填充一侧的边GF替换当前Y直线已填充一侧的边AG参与边排序。边排序的结果是GF、AB、BC、EF、ED、CD。

组合填充时，将和之间、和之间以及和之间进行填充，和之间以及和之间不填充，填充示意图如图3(d)所示。

当时，如图2(f)所示，Y直线与多边形ABCDEFG的交点个数减少为4个。此时四个交点分别是、、、，减少的交点对应的边是AB和BC。将AB和BC从上一次记录的边排序的序列GF、AB、BC、EF、ED、CD中删除，得到本次边排序的结果为GF、EF、ED和CD，对应交点的排序顺序是、、、。

组合填充时，将和之间和和之间进行填充，和之间则不填充，填充示意图如图3(e)所示。

当时，如图2(g)所示，Y直线与多边形ABCDEFG的交点个数减少为2个。此时四个交点分别是、，减少的交点对应的边是ED和CD。将ED和CD从上一次记录的边排序的序列GF、EF、ED和CD中删除，得到本次边排序的结果为GF、EF，对应交点的排序顺序是、。

组合填充时，将和之间，填充示意图如图3(f)所示。

和的填充过程相似，如图2(h)和图3(g)所示。时的填充完成后，执行条件判断，令，此时新的Y大于，填充过程结束。

以上应用具体实施例对本发明的技术方案进行了详细阐述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。同时，以上实施例的说明只是用于帮助理解本发明的核心思想，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处。因此，基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其它实施例，都属于本发明保护的范围。综上所述，本说明书内容不应理解为对本发明的限制。

Claims (6)

1.一种在FPGA中填充非自相交多边形的填充方法，其特征在于，包括如下步骤：

坐标获取步骤，获取多边形各顶点的Y坐标值，得出各顶点的Y坐标值的最大值点Ymax、最小值点Ymin以及非极值点，并对多边形各边进行编号；

交点计算步骤，获取Y=Ymin的直线与多边形各边的交点的X坐标值并记录交点个数以及交点所在边的编号；

交点排序及边排序步骤，对交点的X坐标值进行排序，然后按照X值由小到大的顺序对交点进行交点排序，并对交点所在边依据交点排序的顺序进行边排序，记录边排序后各个边编号的顺序；

组合填充步骤，对排序后的交点从x值最小的交点开始每两个组合为一组，每个交点不重复参加组合，同一组的两个交点之间进行填充，其余位置不填充；

条件判断步骤，令Y=Y+1，判断Y是否大于Ymax，

若Y>Ymax时结束填充过程，

若Y不大于Ymax，则返回并执行交点计算步骤，然后进行极值点判断，若交点中不存在非极值点的顶点或交点中存在非极值点的顶点但该顶点拥有的两条边均在当前Y直线的同一侧时，则执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程，

若交点中存在非极值点的顶点且该顶点拥有的两条边在当前Y直线的两侧时，则进行交点合并及边替换，然后执行交点排序及边排序步骤及之后的步骤，直至Y>Ymax时结束填充过程。

2.根据权利要求1所述的一种在FPGA中填充非自相交多边形的填充方法，其特征在于，当Y>Ymin且Y≤Ymax时，所述交点排序及边排序步骤存在简化算法，所述简化算法首先对当前Y直线与多边形的交点个数与上一次记录的交点个数进行比较，然后根据交点个数变化的情况执行相应简化算法：

当交点个数与上一次记录的交点个数相同，且上一次记录的交点不存在极值点的顶点，则交点对应的边顺序就是本次交点排序的顺序；

当交点个数与上一次记录的交点个数相同，且上一次记录的交点存在极值点的顶点，则对极值点的顶点具有的两条边按照对应交点的排序顺序进行排序，然后将所述两条边排序的结果作为整体参与边排序；

当交点个数比上一次记录的交点个数多时，对交点进行排序，以交点排序的结果作为交点所在的边的排序结果，将此交点所在的边的排序结果作为整体参与边排序；

当交点个数比上一次记录的交点个数少时，将减少的交点对应的边从边排序的序列中删除，剩余的边排序的序列保持不变，边排序的结果是对应交点的排序顺序。

3.根据权利要求2所述的一种在FPGA中填充非自相交多边形的填充方法，其特征在于：当交点个数与上一次记录的交点个数相同，且上一次记录的交点存在极值点的顶点，对极值点的顶点具有的两条边排序的排序结果若保持与上一次记录的边排序结果中此两条边的排序顺序一致时，则无需进行边排序，上一次记录的边排序结果即为本次的边排序结果。

4.根据权利要求1所述的一种在FPGA中填充非自相交多边形的填充方法，其特征在于，所述交点合并的方法是：将非极值点的顶点对应的两个交点合并为一个，然后进行交点排序。

5.根据权利要求1所述的一种在FPGA中填充非自相交多边形的填充方法，其特征在于，所述边替换的方法是：使用非极值点的顶点拥有的两条边中在当前Y直线未填充一侧的边替换当前Y直线已填充一侧的边参与边排序。

6.根据权利要求1所述的一种在FPGA中填充非自相交多边形的填充方法，其特征在于：所述填充方法适用于任意边数的非自相交多边形。