Shape Approximation of Printed Images in VLSI Design

vlsi;polygon;approximation

Han, Khine ; Wong ; Martin D.F.

关键词: vlsi;    polygon;    approximation;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/11990/Han_Khine.pdf?sequence=2&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices.For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.