Application of Scan Line Methodology to Perform
Metric Operations in DRC

Introduction

This article describes application of the scan-line method to metric operations in DRC. This method is known to be very fast and it is widely used as a powerful engine in computational geometry algorithms including DRC algorithms [1, p.79]. We show here that the same scan-line based engine can be used for almost all DRC operations which opens very attractive possibilities for optimization of the DRC script execution process. Here we present an approach that allows us to the extend scan-line technique capabilities to make it useful for building algorithms of metric operations. The methodology described here is implemented in Savage DRC .

Formalization of Various DRC Operations as Checking of Distances between Segments

Formalization of Metric Operations
Among all DRC operations we consider those intended to check metric correlations between different objects of topology. Such operations here are referred to as metric operations. Although every topology consists of polygons we suggest to define DRC operations in terms of segments which are edges of the polygons. If we consider only basic metric operations, such as Width, InDistance and OutDistance it is easy to show that for any of them a logical condition C(s1, s2) on segments s1 and s2 could be formulated. Then such operation on some set of polygons reduces to checking of distances between segments (edges of initial polygons) which satisfy the C condition. For example, in case of metric operation Width the simplified condition C(s1, s2) could be formulated as follows: checking of distance between segments s1 and s2 is performed if and only if these segments represent internal edges of the same polygon. Here we consider the "segment" as a data structure which includes not only the pair of points but also the reference to the polygon it belongs to and the side of the segment which lies inside the polygon. Thereafter this data structure is referred to as an extended segment.

Determination of Distance between two segments
We will restrict consideration here only to those DRC operations that check the condition "distance is not less than r units". The distance between two segments s1 and s2 is defined here as length of the shortest segment that connects s1 and s2. Then, for the distance between s1 and s2 to be not less than r units it is necessary and sufficient that no point of segment s2 lies in the neighborhood of radius r around segment s1 (see Figure 1). A similar neighborhood can be easily built for entire polygon, as it equals to external part of the union of neighborhoods of its edges. It could be an internal part of the union for other DRC operations. This kind of neighborhood is most widely used by various DRC programs when it comes to the checking of metric correlations.

Figure 1. An example of defining neighborhood of a segment.

Application of Scan-Line Method in Enumeration of Segments Subject to Check

Structure of scanning algorithm
Consider the building of an algorithm that checks DRC metric correlations which is based on scan-line technique. It is known that this technique could be naturally used to build algorithms for DRC operations from Logic and Select groups [1, p.110] or for determination of all the points where polygons of topology intersect each other [1, p.85]. Therefore it can be shown that considering the initial topology as a set of extended segments it is possible to divide the algorithm of DRC operations into two distinct modules: the universal abstract algorithm of scanning of topology with horizontal line and the block of calculation of these operations. The output of the first module is the input of the latter one and the data exchange between these modules occurs at only one point in which the scanning algorithm calls the block of logic operations once for each scanning level passing there piece of information called scan-line status [2, p.11]. The scan-line status is defined as pair (y, S) consisting of vertical coordinate of scan-line and set S of all segments of topology that intersect the scan-line including those segments which lie on the scan-line with one or both of their ends (see Figure 2). Let us assume that coordinates (x1, y1, x2, y2) of every segment in set S satisfy the condition y1 < y2. Scan levels are defined by endpoints of segments and their intersection points. In order to perform DRC metric checks it is necessary to analyze information within some neighborhood of every object of topology. In our case those objects are extended segments. It is easy to see that the information that constitutes the scan-line status defined above is not sufficient for exhaustive analysis of neighborhoods of all segments from the status. Therefore it is important to find a generalization of scan-line algorithm that allows implementation of Logic or Select operation as well as metric operations. It is also important to inherit the module structure of the original algorithm to the new one.

Figure 2. Scan line status at a given moment is defined
as the set of segments intercepting the scan line.

Scan-stripe technique

The scan approach Savage employs differs from the original one only in organization of information about scan-line status. The scanning itself is carried out the same way as before. But while the original scan-line status (namely, set S) includes only those segments that intersect the line, the generalized status includes segments that have common points with a horizontal stripe which bottom border coincides with the scan-line and which width is equal to r, where r is the parameter of the metric operation. Thereafter this new status is referred to as status of scan-stripe of width r (see Figure 3). The three elements (y, r, S) describe scan-stripe status. Obviously, when r = 0 scan-stripe status coincides exactly with status of corresponding scan-line. As before, scan levels are defined by endpoints of segments and their intersection points. It is easy to demonstrate that in order to reveal for every scanning level with scan-stripe status (y, r, S) all the violations of DRC metric correlations in given topology it is sufficient to consider only neighborhoods of radius r of segments from so called subset of active segments of set S (denoted as P(S)) and check if these neighborhoods are intersected by any other segments from set S. Subset of active segments of set S consists of non-horizontal segments from S that lie inside scan-stripe with one or both of their ends:

P(S) = { (x1, y1, x2, y2) from S |
 x1 not equal x2, y < y1 < y + r  or  y < y2 < Y + r }

A = B .or. C;
D = E .and. F;
G = A .xor. D;