Steiner tree based approach for polygon fracturing
AssigneeSynopsys, Inc.
InventorsQing Su, Yongqiang Lu, Charles C. Chiang
Life of this patent
Estimating the term…
Abstract
Roughly described, a method for mask data preparation is described, for use with a preliminary mask layout that includes a starting polygon, the vertices of the starting polygon including I-points (vertices of the starting polygon having an interior angle greater than 90 degrees), including steps of developing a rectilinear partition tree on at least the I-points of the starting polygon, and using the edges of the partition tree to define the partition of the starting polygon into sub-polygons for mask writing.
Claims38
A method for mask data preparation, for use with a preliminary mask layout that includes a starting polygon, the starting polygon consisting of a plurality of boundary segments connecting pairs of starting polygon vertices, the starting polygon having an interior,
- wherein the vertices of the starting polygon include at least one I-point each having an interior angle strictly greater than 90 degrees, the method comprising:
- by a computer system, constructing a spanning tree connecting all the I-points of the starting polygon as well as all the R-points of the starting polygon, the R-points being all boundary of the starting polygon which do not coincide with a vertex, and which are disposed rectilinearly across the starting polygon interior from one of the I-points;
- traversing the spanning tree recursively according to the tree structure;
- in dependence upon the step of traversing, developing a rectilinear partition tree having a plurality of nodes and a plurality of edges connecting pairs of the nodes, the plurality of nodes including all I-points of the starting polygon, the plurality of edges including at least one connected to each of the I-points;
- and
- outputting a plurality of sub-polygons which collectively partition the starting polygon, all the sides of all of the sub-polygons lying on either a boundary of the starting polygon or an edge of the partition tree or both.
A system for mask data preparation, for use with a preliminary mask layout that includes a starting polygon, the starting polygon consisting of a plurality of boundary segments connecting pairs of starting polygon vertices, the starting polygon having an interior,
- wherein the vertices of the starting polygon include at least one I-point each having an interior angle strictly greater than 90 degrees, the system comprising:
- means for constructing a spanning tree connecting all the I-points of the starting polygon as well as all the R-points of the starting polygon, the R-points being all points on a boundary of the starting polygon which do not coincide with a vertex, and which are disposed rectilinearly across the starting polygon interior from one of the I-points;
- means for traversing the spanning tree recursively according to the tree structure;
- means for developing, in dependence upon the means for traversing, a rectilinear partition tree having a plurality of nodes and a plurality of edges connecting pairs of the nodes, the plurality of nodes including all I-points of the starting polygon, the plurality of edges including at least one connected to each of the I-points;
- and
- means for outputting a plurality of sub-polygons which collectively partition the starting polygon, all the sides of all of the sub-polygons lying on either a boundary of the starting polygon or an edge of the partition tree or both.
Dependencies are inferred from the claim text.