| 主权项 |
1.一种基于倒序树扫描线的版图验证技术，涉及到层次处理边中判断边的类别和计算边的状态，具体步骤如下：(1)层次预处理在每个单元中，形成所有图形对应边的ILT(版图倒序树)。形成ILT的过程采用版图层次结构自顶向下投影的步骤，投影操作分为：图形与Instance边框重合的情况以及Instance与Instance有重合部分的情况两类，其中Instance与Instance有重合部分时，要利用递归投影的方法，寻找所有可能有重叠的图形。步骤1的详细实现在程序DPgoa.cpp和UTcell.cpp中。(2)每个单元自底向上采用扫描线算法处理。在每条扫描线上，对边按照Y坐标的大小排序，垂直边不参与运算。排序的主要目的是为下一步计算边的状态做准备。步骤2的详细实现在程序SCscan.cpp中。(3)扫描线上自底向上逐个计算每条边的状态，状态值采用多个ILT表示，状态的记录分为两类，分别是：当本边存在时的状态存在状态(ExistStatusILT)和本边不存在时的状态(NonExistStatusILT).其中ILT存在状态(ExistStatusILT)根据不同的状态值采用多个的ILT存储，NonExistStatusILT也根据不同的状态值采用多个的ILT存储。步骤3的详细实现在程序UTedge.h中。(4)每条halo边的状态值仅取决于它的直接前驱边，与其它边的状态无关。这是由于，状态对应的ILT详细记录了它之前所有边的存在与不存在的情况。(5)通过前一条边存在状态和不存在状态的的ILT与本边的halo做逻辑”与”运算得到本边的存在状态。本边存在状态的ILT＝前一条边的存在状态(ExistStatusIL)“与”本边的halo+ 前一条边的不存在状态(NonExistStatusIL)“与”本边的halo本边存在状态的数值＝前一条边的状态数值+1(如果本边方向为正)。本边存在状态的数值＝前一条边的状态数值-1(如果本边方向为负)。步骤5的详细实现在程序SCstatus.cpp中(6)通过前一条边存在状态和不存在状态的ILT与本边ILT做逻辑”减”运算得到本边不存在的状态。本边不存在状态的ILT＝前一条边的ILT存在状态(ExistStatus)“减”本边的halo 前一条边的非ILT存在状态(NonExistStatus)“减”本边的halo本边不存在状态的数值＝前一条边的状态数值(不论本边的方向为正或负)。步骤6的详细实现在程序SCstatus.cpp中(7)状态计算的结果在区分内边、外边时，只需判断存在状态的ILT对应的状态值，不必考虑不存在状态的ILT。步骤7的详细实现在程序SClayer.cpp中 |
