The use of a one-dimensional scanline and corner extensions to build two-dimensional geometric constraints in a shapes database.
Original Publication Date: 2004-Dec-14
Included in the Prior Art Database: 2004-Dec-14
Disclosed is a technique for discovering geometric relationships between shapes in the two-dimensional database. This technique uses one-dimensional scanline to construct a topological description of the data relative to the direction perpendicular to the scanline. It then uses the extension of previously viewed corners in combination with a shape-union data structure to build constraints in the direction parallel to the scanline, using information derived from relationships in the orthogonal direction. One embodiment of this idea describes how to form geometric constraints from the purpose of modeling design rules during VLSI layout optimization.
The use of a one-dimensional scanline and corner extensions to build two -dimensional geometric constraints in a shapes database .
In applications that use a two-dimensional computer-aided design (CAD) database, it is frequently necessary to discover geometric relationships between shapes in the database: for example, what shapes appear to the right of a given shape? What shapes appear inside a given shape? One specific example of this is in the optimization of a VLSI design. A standard technique for discovering these relationships involves a one-dimensional scanline. The scanline can be seen as a cutline through the 2-D database. Along this cutline, shape edges that are not parallel to the cutline are seen. This cutline is swept across the entire set of data in the direction perpendicular to the cutline's orientation. By monitoring different events--for example, the start of an edge, the end of an edge, the start of a convex corner--and performing certain actions at these events, a topological description of the data relative to the direction perpendicular to the scanline can be constructed: for any pair of vertical edges, and with a horizontal scanline, we can answer the question, "Which edge lies to the left of the other?" For a vertical scanline, we can answer the question, "Which edge lies above the other?"
This one-dimensional topological description of the data is sufficient for many applications. However, for more complex applications, the one-dimensional nature of the scanline proves to be a significant weakness. For example, in order to build a relationship between two horizontal shape edges and then annotate that relationship with a value or property that depends on the relationship between two vertical edges, there is no simple way to do this using a one-dimensional scanline.
One way to overcome this limitation involves processing the shapes data with a horizontal scanline; saving the position information; and then processing the data again with a vertical scanline; and finally correlating horizontal and vertical relationships between nearby edges. The processing for this is involved and requires significant memory, since both horizontal and vertical relationships must be saved.
Presented here is a technique involving the extension of previously viewed corners in combination with a shape-union data structure that enables the building of constraints in one direction using information derived from relationships in the orthogonal direction. One embodiment of this idea describes how to form geometric constraints for the purposes of modeling design rules during VLSI layout optimization.
The core idea is illustrated by showing a design rule for PC (polysilicon) and RX (diffusion) levels from a VLSI manufacturing technology.
In Figure 1, the overlap value d1 depends on the distance d2: smaller d2 require larger d1 and vice versa.
Figure 2 shows a vertical scanline cutting throug...