Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
2000-03-27
2003-03-18
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C438S942000
Reexamination Certificate
active
06535222
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method of processing a figure and a recorded medium. More particularly, the present invention relates to a graphic method of judging intersection of trapezoidal figures in a step of synthesizing a masking layer in the production of large-scale integrated circuits (LSTs).
2. Description of the Related Art
Fabrication of an LSI includes a step of synthesizing a masking layer. Synthesis of the masking layer is a “graphic OR” process for synthesizing design data with the layer as a unit and removing portions where the figures overlap. There can be further exemplified “AND processing”, “NOT processing” and “XOR processing” in addition to OR processing. The data in the masking layer are expressed as a trapezoid, having parallel upper side and lower side, as a unit. Therefore, figures that are to receive the logical processing, such as OR processing, are trapezoidal figures which are basic figures.
The trapezoidal figures to be put to the logic processing are those figures that overlap one upon the other or are those figures in which one figure is completely included in the other figure. Prior to executing the logic processing, therefore, it is necessary to execute an intersection judgement process concerning whether the trapezoidal figures overlap one upon the other (including one figure being completely included in the other figure as described above).
When it is required to judge the intersecting relationship among a plurality of figures (whether they are overlapping, or whether one figure is completely included in the other figure) as in the step of synthesizing the masking layer, the intersection judgement processing has heretofore been executed for every combination of two figures.
According to the conventional intersection judgement processing executed for every combination of two figures, however, the intersection is judged even for those figures that are located at distant positions on a plane of an X-Y coordinate system on which trapezoidal figures are placed, wastefully consuming processing time and requiring an extended period of time for judging the intersecting relationships of all figures.
A key point for executing the graphic method for judging the intersecting relationship at high speed is to reduce the number of times of executing the intersection judgement processing as much as possible.
SUMMARY OF THE INVENTION
An object of the present invention is to solve the above-mentioned problem and to provide a graphic method capable of judging, at high speed, the intersecting relationships among large number of figures in the synthesis of a masking layer.
In order to solve the above-mentioned problem, the present invention provides a graphic method of judging intersecting relationships among a plurality of trapezoidal figures, having upper and lower sides in parallel with an X-axis, comprising:
a grouping step for classifying those trapezoidal figures having the lower sides of the same Y-coordinate values into the same groups, sorting the groups based on the Y-coordinate values of said lower sides, sorting the trapezoidal figures included in said groups based on minimum X-coordinate values of the trapezoidal figures, and storing them;
a to-be-judged group-determining step for using any one of said groups as a to-be-judged group in order of sorting;
an intra-group judging step for using any one of said trapezoidal figures included in said to-be-judged group as a to-be-judged figure in order of sorting, using any one of the trapezoidal figures in said to-be-judged group sorted after said to-be-judged figure as a to-be-compared figure successively in order of sorting, and repetitively executing intersection judgement processing only when a maximum X-coordinate value of the to-be-judged figure is greater than a minimum X-coordinate value of the to-be-compared figure while comparing the maximum X-coordinate value of the to-be-judged figure with the minimum X-coordinate value of said to-be-compared figure until the maximum X-coordinate value of the to-be-judged figure becomes smaller than the minimum X-coordinate value of the to-be-compared figure or until the to-be-compared figure disappears; and
an inter-group judging step for using any one of said groups sorted before said to-be-judged group as a to-be-compared group in order of sorting, comparing the Y-coordinate values of the lower sides of the trapezoidal figures included in said to-be-judged group with a maximum Y-coordinate value of a trapezoidal figure included in said to-be-compared group, and executing the intersection judgement processing between the trapezoidal figures included in said to-be-judged group and the trapezoidal figures included in said to-be-compared group only when the Y-coordinate value of the lower side of said to-be-judged group is smaller than said maximum Y-coordinate value of said to-be-compared group;
said to-be-judged group-determining step through up to said inter-group judging step being repeated until there is no group that can be used as said to-be-judged group in said to-be-judged group-determining step.
In the intra-group judging step, the time-consuming intersection judgement processing is not executed for the figures from the first time but, instead, a maximum X-coordinate value of a to-be-judged figure is compared with a minimum X-coordinate value of a to-be-compared figure, which is easy to execute, and the intersection judgement processing is executed only when the maximum X-coordinate value of the to-be-judged figure is larger than the minimum X-coordinate value of the to-be-compared figure, i.e., only when there is a probability of intersection. Therefore, the intersection judgement processing is not executed for the figures which apparently have no probability of intersection. similarly, further, the intersection judgement processing is terminated in the to-be-judged group when the maximum X-coordinate value of the to-be-judged figure becomes smaller than the minimum X-coordinate value of the to-be-compared figure and there is apparently no probability of intersection. Thus, the processing time can be shortened as compared with when the intersection judgement processing is executed for all of the figures in the to-be-judged group.
In the inter-group judging step, further, a Y-coordinate value of the lower side of a trapezoidal figure included in the to-be-judged group is compared with a maximum Y-coordinate value of a trapezoidal figure included in the to-be-compared group, which is easy to process, at the time of judging the intersection between the two groups, i.e., between trapezoidal figure in the to-be-judged group and the trapezoidal figure in the to-be-compared group, and the intersection judgement processing is executed between the trapezoidal figure included in the to-be-judged group and the trapezoidal figure included in the to-be-compared group only when the Y-coordinate value of the lower side of the to-be-judged group is smaller than the maximum Y-coordinate value of the to-be-compared group, i.e., only when there is a probability of intersection. Therefore, the intersection judgement processing is not executed for the trapezoidal figures included in the groups which apparently have no probability of intersection Thus, the processing time can be shortened as compared with when the intersection judgement processing is executed for all of the trapezoidal figures included in the two groups.
In the present invention, further, the inter-group judging step uses any one of the trapezoidal figures included in the to-be-judged group as a to-be-judged figure successively in order of sorting, uses any one of the trapezoidal figures included in the to-be-compared group as a to-be-compared figure successively in order of sorting when the Y-coordinate value of the lower side of the to-be-judged group is smaller than a maximum Y-coordinate value of the to-be-compared group, judges the intersecting relationship between the to-be-judged figure and the to-be-compared figure along the direction of
McCartney Linzy
Pennie & Edmonds LLP
Shinko Electric Industries Co. Ltd.
Zimmerman Mark
LandOfFree
Graphic method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Graphic method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graphic method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3008381