Browse Prior Art Database

LSI Mask Shape Determination

IP.com Disclosure Number: IPCOM000089160D
Original Publication Date: 1977-Sep-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 22K

Publishing Venue

IBM

Related People

Goodwin, DA: AUTHOR [+3]

Abstract

The SHADOW of a polygon (all LSI (large-scale integration) mask shapes are polygons) is the minimum orthogonal rectangle enclosing it. Current Method of Shape Association: 1. Shadow test: if the shadows do not touch/intersect, then enclosed polygons do not, and the remaining steps are unnecessary. 2. Check all pairs of lines, one from each polygon, for intersection to test for polygons intersecting. 3. If no intersection is found, then check whether either polygon is entirely within the other.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 72% of the total text.

Page 1 of 3

LSI Mask Shape Determination

The SHADOW of a polygon (all LSI (large-scale integration) mask shapes are polygons) is the minimum orthogonal rectangle enclosing it.

Current Method of Shape Association:
1. Shadow test: if the shadows do not

touch/intersect, then enclosed

polygons do not, and the remaining steps are unnecessary.
2. Check all pairs of lines, one from each polygon, for

intersection to test for polygons intersecting.
3. If no intersection is found, then check whether either

polygon is entirely within the other.

It is the second step where execution times are becoming more and more unacceptable due to increased LSI complexity, i.e., more shapes, shapes having more vertices, and complex shapes having large shadows. This shadow describes a faster method of performing the associations. First, a method is described in which one polygon is reduced by excluding portions which can readily be determined as not intersecting the other. Then the procedure to replace step 2 above is described making use of the polygon reduction. Reducing Polygon P, With Respect to Shadow S.

Lines of p outside S are deleted to leave only that part of polygon P which intersect with a polygon in S. All points are in one of the regions shown in the figure below. The points on the boundaries are

(Image Omitted)

defined to be in the more central section.

Take each line of P in turn; then the type of action depends on the region of the figure of its end points.

Type Starting Finishing Action A 1 1, 2, 3, 4, 7 no intersection, set delete flag for line.

B 1 5 intersects shadow, line is retained.

C 1 6, 8, 9 possibly intersects shadow, check for

intersection with AB,AD,

delete if it

intersects neither.

D 2 1, 2, 3 as A.

E 2 5 as B.

F 2 4, 6, 7, 9 possibly intersects shadow, delete if no

intersection with AB.

G 2 8 if colinear with AD or BC, line is retained.

Otherwise P must intersect

1

Page 2 of 3

any polygon in S

- intersection check is

terminated immediately.

H 5 any as...