Robust boolean operations in design rule checking

Details Robust boolean operations in design rule checking Robust boolean operations in design rule checking

2000-10-25

2004-02-10

Brier, Jeffery (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Graphic manipulation

C345S624000

Reexamination Certificate

active

06690385

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to fabrication of integrated circuits and more particularly to a process for reducing failures due to round-off errors during design rule checking algorithms.
BACKGROUND OF INVENTION
Integrated circuits must be layed out so that components (i.e., resistors, transistors, diodes, capacitors, and the like) and wiring between the components do not intersect at undesired locations but do have sufficient spacing between them to operate reliably. To meet these requirements, integrated circuit layout is performed using a computer program applying a design rule checking (DRC) algorithm. DRC can require checking millions or even tens of millions of geometric shapes to verify that they satisfy the closeness requirements (i.e., design rules) for reliable operation of the integrated circuit being designed.
DRC algorithms typically perform Boolean operations such as intersection, union, and difference using polygons to represent the components and wiring on the integrated circuit. In many DRC implementations, the polygons are represented using long or integer coordinates. When Boolean operations such as intersection, union, and difference are performed using these polygons, vertex coordinates are computed by intersecting two edges using floating point computations. Then, these vertex coordinates are rounded to long or integers for the output polygon. As a result of this rounding, the output polygons can intersect spuriously. For example, an output polygon can self-intersect to create a bow-tie, or an inside loop can intersect an outside loop that is supposed to enclose the inside loop. These spurious intersections, create undefined or ill defined point-sets, resulting in ambiguous or wrong answers for DRC operations.
Many DRC algorithms operate on the assumption that the output of the Boolean operations that form the foundation of these algorithms are regular and well-defined point sets, and that these point-sets are defined by well-defined polygonal boundaries. Round-off errors during Boolean computations can cause algorithm failures without warning. These undetected errors can cause severe consequences, including wasted computation time due to ambiguous or wrong results or even defective dies due to undetected errors.
The importance of overcoming the various deficiencies noted above is evidenced by the extensive technological development directed to the subject, as documented by the relevant patent and technical literature. Several approaches disclosed in the technical literature focus on minimizing round-off errors in geometric computations. One approach uses a statistical approach to minimize errors, as described in “Recipes for Geometry & Numerical Analysis—Part I: An Empirical Study,” by Dobkin et al., Proceedings of the ACM Symposium on Computational Geometry, page 93 (1988). Another approach provides a method for minimizing the effect of round-off error by using least significant bit calculations, as described in “Numerical Stability of Simple Geometric Algorithms in the Plane,” by Ottmann et al., Proceedings of the ACM Symposium on Computational Geometry, page 163 (1993). Yet another approach uses minimum feature size for Boolean intersections, as described in “Consistent Calculations for Solids Modeling,” by Segal et al., Proceedings of the ACM Symposium on Computational Geometry, page 29 (1985). These approaches minimize, but do not eliminate, rounding errors. Because rounding errors are not eliminated, they can still cause problems for DRC algorithms.
Other approaches attempt to eliminate spurious intersections caused by round-off error, but are very expensive and difficult to implement due to memory requirements, inefficient computational methods, and quantity of computations. “Epsilon Geometry: Building Robust Algorithms for Imprecise Computations,” Guibas et al., Proceedings of the ACM Symposium on Computational Geometry, page 208 (1989), teaches a method using a fuzzy tool for topological consistency checking. “Geometric and Solid Modeling,” by C. Hoffmann, pages 111-53 (Morgan Kaufmann Publishers, Inc. 1989), attempts a topological reasoning method for maintaining topological consistency by using non-redundancy. “Efficient Exact Arithmetic for Computational Geometry,” Fortune et al., ACM Symposium on Conceptual Geometry, page 163 (1993), advocates computations in the exact precision domain. “Interval Methods for Processing Geometric Objects,” Mudur et al., IEEE Computer Graphics and Applications, 4(2):7 (1984), teaches an interval arithmetic approach for computing curve intersections using two bounds for each integer. “Finite-Resolution Computational Geometry,” Greene et al., Proceedings of Twenty-Seventh Annual IEEE-FOCS Conference, page 143 (1986), uses an algorithm for line intersection using number theoretic algorithms. Each of these approaches requires at least one of excess data storage, inefficient algebraic systems, and excess computations—making the approaches prohibitively expensive to implement in a DRC algorithm.
Yet another approach is disclosed in “Verifiable Implementations of Geometric Algorithms Using Finite Precision Arithmetic,” V. Milenkovic, in
Geometrical Reasoning
, pages 377-401 (D. Kapur & J. Mundy eds., MIT Press, 1989). Milenkovic teaches a method for eliminating spurious intersections of two separate polygons by cracking edges at any vertex (v
i
) whose coordinate location is within an error value (&egr;) of any edge (e
1
, e
2
, e
3,
, and so on). The error value (&egr;) is defined as the maximum possible error, which is a function of the maximum round-off and the number of arithmetic operations (for DRC algorithms, the number of arithmetic operations can be in the millions or even tens of millions). Each edge which is within &egr; of a vertex of the other polygon is then converted to multiple new edges having endpoints at each of the vertices that were within &egr; of that edge. Because this edge cracking can create new edge-vertex pairs within the error value (&egr;), the process is repeated until no further edge cracking is possible.
Although this method eliminates certain spurious intersections, it may cause many more edge cracks than are necessary (i.e., the proximity of the edge-vertex pair would not cause spurious intersections, because the vertex would not be rounded off to the opposite side of the edge or the particular edge-vertex proximity would be eliminated by a Boolean operation). Unnecessary edge cracks would cause a DRC program to expend excess memory and computation time. In addition, unnecessary edge cracking can cause unwarranted distortion of the geometric shapes used in a DRC application.
Therefore, an object of the present invention is to provide a process for preventing failures due to round-off during design rule checking algorithms. It is a further object of the present invention to provide a process for preventing failures due to round-off during design rule checking algorithms which requires minimum memory and computational time.
SUMMARY OF THE INVENTION
To achieve these and other objects, and in view of its purposes, the present invention provides a process for proximity-based rounding. A vertex which is close to an edge for which it is not an endpoint is embedded on that edge. The edge is then converted to two edges, each having one of the original endpoints and both having the embedded vertex as the other endpoint.
In one embodiment of the present invention, a design rule checking algorithm uses proximity-based rounding after a Boolean operation is performed on input polygons to produce an output polygon. Each vertex of the output polygon is checked for proximity to each edge of the output polygon by determining whether the vertex is located within an integer box through which the edge passes. If so, the vertex is embedded on the edge. Following proximity-based rounding, the coordinates (vertices) of the output polygon are rounded to integers. Because the vertex and the point embedded on the edge in proximity to the vertex are now the same point, they

Affiliated with

Also associated with

Rating

Robust boolean operations in design rule checking does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Robust boolean operations in design rule checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust boolean operations in design rule checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3337462