Locating a field of view in which selected IC conductors are unobscured

Claim 2

In a system comprising means for supporting an IC device having multiple physical layers and multiple internal nets, and controllable positioning means for positioning a field of view relative to the device, a method of positioning the field of view relative to the device such that multiple, selected nets of the device are-within the field of view, comprising the steps of: a. preparing a processed data set which (1) describes each physical layer of the device as a plurality of reduced polygons, each reduced polygon having dimensions at least as great as a predetermined minimum feature dimension, and (2) associates each of the reduced polygons with a physical layer of the device and with at least one net of the device; b. for each selected net, preparing a transformed data set which describes a plurality of dilated polygons associated with the selected net, each dilated polygon defining the periphery of a region encompassed by the field of view when a point within the field of view is traced around the periphery of a reduced polygon; c. mapping a bit plane for each selected net, each mapped bit plane defining the two-dimensional extent of dilated polygons associated with the selected net; d. identifying any two-dimensional overlap regions over which a plurality of the dilated polygons defined by the bit planes overlap one another; and e. if at least one said overlap region is identified, controlling said controllable positioning means to position the field of view relative to said device at a location which corresponds to at least one said overlap region.

Claim 3

The method of claim 1, wherein said step of preparing a processed data set comprises the steps of: retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a concave polygon; and dividing each concave layout polygon into a plurality of convex reduced polygons.

Claim 4

The method of claim 1, wherein said step of preparing a processed data set comprises the steps of: retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a complex polygon; and reducing each complex layout polygon to a plurality of trapezoids to thereby produce said reduced polygons.

Claim 5

The method of claim 1, wherein said step of preparing a processed data set comprises the steps of: retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a complex polygons; and approximating each complex layout polygon as a plurality of rectangles to thereby produce said reduced polygons.

Claim 6

The method of claim 1, wherein said step of preparing a processed data set further comprises the steps of: retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; identifying portions of the layout polygons describing one physical layer of the device which are not occluded by layout polygons describing another physical layer of the device; and modifying the description of said layout polygons to include only said identified portions to thereby produce said reduced polygons.

Claim 7

The method of claim 1, wherein said step of preparing a processed data set further comprises the steps of: i. retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; ii. reducing said layout polygons by approximating the layout polygons as a plurality of simple trapezoids, each simple trapezoid being associated with a physical layer of the device; iii. expanding each simple trapezoid associated with a first physical layer of the device by a predetermined minimum separation distance to thereby produce an expanded trapezoid; iv. identifying portions of the trapezoids associated with a second physical layer of the device which are not occluded by the expanded trapezoids of said first physical layer; and v. modifying the description of said trapezoids associated with the second physical layer of the device to include only said identified portions to thereby define a plurality of said reduced polygons.

Claim 8

The method of claim 6, wherein said step of preparing a processed data set further comprises the steps of: vi. expanding each simple trapezoid associated with the second physical layer of the device by a predetermined minimum separation distance to thereby produce an expanded trapezoid; vii. identifying portions of the trapezoids associated with a third physical layer of the device which are not occluded by the expanded trapezoids of the second physical layer; and v. modifying the description of said trapezoids associated with the third physical layer of the device to include only said identified portions to thereby define a plurality of said reduced polygons.

Claim 9

The method of claim 1, wherein said step of preparing a processed data set further comprises the steps of: retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; and approximating each complex layout polygon as a plurality of fixed-width lines representing said reduced polygons.

Claim 10

The method of claim 1, wherein said step of preparing a processed data set comprises the steps of: i. retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; ii. approximating the layout polygons as trapezoids; and iii. associating each of the trapezoids with a physical layer of the device and with a net of the device.

Claim 11

The method of claim 9, wherein said step of preparing a processed data set further comprises the step of calculating at least one bounding box for each net.

Claim 12

The method of claim 9, wherein said step of preparing a processed data set further comprises the step of, for at least one net having associated trapezoids which are also associated with multiple layers of the device, deleting at least one trapezoid associated with a lower layer of the device and retaining at least one trapezoid associated with an upper layer of the device, whereby the trapezoids which are retained comprise said plurality of reduced polygons.

Claim 13

The method of claim 1, wherein said step of preparing a transformed data set comprises the steps of: i. identifying a bounding box for each selected net; ii. defining a bounding region corresponding to the union of the bounding boxes of the selected nets; and iii. for each selected net, dilating the reduced polygons which are located within the bounding region and which are associated with the net, to thereby produce a plurality of dilated polygons.

Claim 14

The method of claim 1, wherein said step of mapping a bit plane for each selected net comprises the steps of: i. setting a bit of the bit plane to a first value for each coordinate position of the bit plane which lies with the extent of a dilated polygon associated with the net; and ii. setting a bit of the bit plane to a second value for each coordinate position of the bit plane which lies outside the extent of the dilated polygon associated with the net.

Claim 15

The method of claim 13, wherein said step of identifying at least one two-dimensional overlap region comprises the steps of: i. preparing a binary word for each coordinate position of the bit planes, the binary word comprising one bit from each bit plane; and ii. examining said binary words to identify said at least one two-dimensional overlap region.

Claim 16

The method of claim 13, wherein said step of identifying at least one two-dimensional overlap region comprises the steps of: i. assigning to each bit plane a respective bit position of a binary word, the assigned bit position being determined by an ordered priority of the selected nets; ii. preparing a binary word for each coordinate position of the bit planes, the binary word comprising one bit from each bit plane and the bits of the binary word being ordered in accordance with the assigned bit positions; and iii. evaluating said binary words to identify said at least one two-dimensional overlap region.

Claim 17

The method of claim 1, wherein said system further includes second controllable means for positioning a focus point within the field of view, the method further comprising the step of: f. controlling said second controllable means to position the focus point at a plurality of said selected nets of the device within the positioned field of view.

Claim 18

The method of claim 1, wherein said system further includes second controllable means for positioning a focus point within the field of view, the method further comprising the steps of: f. identifying a portion of a selected net at which the focus point is to be positioned, such that said portion is spaced apart from neighboring nets of the device by a minimum separation distance; and g. controlling said second controllable means to position the focus point at said identified portion of a net.

Claim 19

The method of claim 17, wherein said step of identifying a portion of a net at which the focus point is to be positioned comprises the steps of: i. expanding each polygon lying within the field of view to produce a respective expanded polygon; ii. identifying regions of overlap of the expanded polygons; iii. identifying portions of a net at which the focus point is to be positioned, such that said portions are furthest separated from said regions of overlap.

Claim 20

The method of claim 1, further comprising the step of repetitively performing steps b.-d. for varying field of view dimensions to determine a minimum field of view dimension for which the field of view can be positioned such that the selected nets are within the field of view.

Claim 21

The method of claim 1, wherein the field of view of said system is of adjustable dimension, the method further comprising the steps of: i. calculating a bounding box for each selected net; ii. determining whether bounding boxes for the selected nets contain any zones of mutual overlap; iii. if the bounding boxes for the selected nets contain at least one zone of mutual overlap, selecting an initial field of view dimension prior to commencing step b.; iv. performing steps b.-d. to identify any of said overlap regions; v. if at least one said overlap region is identified in step iv., iteratively decreasing the field of view dimension and repeating steps b.-d. to determine a minimum field of view dimension for which the field of view can be positioned such that the selected nets are within the field of view; and vi. if no said overlap region is identified in step iv., iteratively increasing the field of view dimension and repeating steps b.-d. to determine a minimum field of view dimension for which the field of view can be positioned such that the selected nets are within the field of view.

Claim 22

Apparatus, comprising: a. means for supporting an IC device having multiple physical layers and multiple internal nets; b. means defining a field of view; c. controllable positioning means for positioning the field of view relative to the device; and d. means for controlling said controllable positioning means to position the field of view relative to the device such that selected nets of the device are within the field of view, comprising: i. means for preparing a processed data set which (1) describes each physical layer of the device as a plurality of reduced polygons, each reduced polygon having dimensions at least as great as a predetermined minimum feature dimension, and (2) associates each of the reduced polygons with a physical layer of the device and with at least one net of the device; ii. means for preparing a transformed data set which describes a plurality of dilated polygons associated with each selected net, each dilated polygon defining the periphery of a region lying within the field of view when a point within the field of view is traced around the periphery of a reduced polygon; iii. means for mapping a bit plane for each selected net, each mapped bit plane defining the two-dimensional extent of dilated polygons associated with the net; iv. means for identifying at least one two-dimensional overlap region over which a plurality of the dilated polygons defined by the bit planes overlap one another; and v. means for controlling said controllable positioning means to position the field of view relative to said device at a location which corresponds to at least one said overlap region.

Claim 23

Apparatus, comprising: a. means for supporting an IC device having multiple physical layers and multiple internal nets; b. means defining a field of view; c. controllable positioning means for positioning the field of view relative to the device; and d. means for controlling said controllable positioning means to position the field of view relative to the device such that selected nets of the device are within the field of view, comprising: i. means for preparing a processed data set which (1) describes each physical layer of the device as a plurality of reduced polygons, each reduced polygon having dimensions at least as great as a predetermined minimum feature dimension, and (2) associates each of the reduced polygons with a physical layer of the device and with at least one net of the device; ii. means for preparing a transformed data set which describes a plurality of dilated polygons associated with each selected net, each dilated polygon defining the periphery of a region lying within the field of view when a point within the field of view is traced around the periphery of a reduced polygon; iii. means for mapping a bit plane for each selected net, each mapped bit plane defining the two-dimensional extent of dilated polygons associated with the net; iv. means for identifying at least one two-dimensional overlap region over which a plurality of the dilated polygons defined by the bit planes overlap one another; and v. means for controlling said controllable positioning means to position the field of view relative to said device at a location which corresponds to at least one said overlap region.

Claim 24

The apparatus of claim 21, wherein said means for preparing a processed data set comprises: means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a concave polygon; and means for dividing each concave layout polygon into a plurality of convex reduced polygons.

Claim 25

The apparatus of claim 21, wherein said means for preparing a processed data set comprises: means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a complex polygon; and means for reducing each complex layout polygon to a plurality of trapezoids to thereby produce said reduced polygons.

Claim 26

The apparatus of claim 21, wherein said means for preparing a processed data set comprises: means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons, at least one of said layout polygons being a complex polygon; and means for approximating each complex layout polygon as a plurality of rectangles to thereby produce said reduced polygons.

Claim 27

The apparatus of claim 21, wherein said means for preparing a processed data set further comprises: means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; means for identifying portions of the layout polygons describing one physical layer of the device which are not occluded by layout polygons describing another physical layer of the device; and means for modifying the description of said layout polygons to include only said identified portions to thereby produce said reduced polygons.

Claim 28

The apparatus of claim 21, wherein said means for preparing a processed data set further comprises: i. means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; ii. means for reducing said layout polygons by approximating the layout polygons as a plurality of simple trapezoids, each simple trapezoid being associated with a physical layer of the device; iii. means for expanding each simple trapezoid associated with a first physical layer of the device by a predetermined minimum separation distance to thereby produce an expanded trapezoid; iv. means for identifying portions of the trapezoids associated with a second physical layer of the device which are not occluded by the expanded trapezoids of said first physical layer; and v. means for modifying the description of said trapezoids associated with the second physical layer of the device to include only said identified portions to thereby define a plurality of said reduced polygons.

Claim 29

The apparatus of claim 26, wherein said means for preparing a processed data set further comprises: vi. means for expanding each simple trapezoid associated with the second physical layer of the device by a predetermined minimum separation distance to thereby produce an expanded trapezoid; vii. means for identifying portions of the trapezoids associated with a third physical layer of the device which are not occluded by the expanded trapezoids of the second physical layer; and v. means for modifying the description of said trapezoids associated with the third physical layer of the device to include only said identified portions to thereby define a plurality of said reduced polygons.

Claim 30

The apparatus of claim 21, wherein said means for preparing a processed data set further comprises: means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; and means for approximating each complex layout polygon as a plurality of fixed-width lines representing said reduced polygons.

Claim 31

The apparatus of claim 21, wherein said means for preparing a processed data set further comprises: i. means for retrieving a stored data set which describes each physical layer of the device as a plurality of layout polygons; ii. means for approximating the layout polygons as trapezoids; and iii. means for associating each of the trapezoids with a physical layer of the device and with a net of the device.

Claim 32

The apparatus of claim 29, wherein said means for preparing a processed data set further comprises means for calculating a bounding box for each net.

Claim 33

The apparatus of claim 29, wherein said means for preparing a processed data set further comprises means, for at least one net having associated trapezoids which are also associated with multiple layers of the device, for deleting at least one trapezoid associated with a lower layer of the device and retaining at least one trapezoid associated with an upper layer of the device, whereby the trapezoids which are retained comprise said plurality of reduced polygons.

Claim 34

The apparatus of claim 21, wherein said means for preparing a transformed data set comprises: i. means for defining a bounding box for each selected net; ii. means for defining a bounding region corresponding to the union of the bounding boxes of the selected nets; and iii. means for dilating, for each selected net, the reduced polygons which are located within the bounding region and which are associated with the net, to thereby produce a plurality of dilated polygons.

Claim 35

The apparatus of claim 21, wherein said means for mapping a bit plane for each selected net comprises: i. means for setting a bit of the bit plane to a first value for each coordinate position of the bit plane which lies with the extent of a dilated polygon associated with the net; and ii. means for setting a bit of the bit plane to a second value for each coordinate position of the bit plane which lies outside the extent of the dilated polygon associated with the net.

Claim 36

The apparatus of claim 33, wherein said means for identifying at least one two-dimensional overlap region comprises: i. means for preparing a binary word for each coordinate position of the bit planes, the binary word comprising one bit from each bit plane; and iii. means for examining said binary words to identify said at least one two-dimensional overlap region.

Claim 37

The apparatus of claim 34, wherein said means for identifying at least one two-dimensional overlap region comprises: i. means for assigning to each bit plane a respective bit position of a binary word, the assigned bit position being determined by an ordered priority of the selected nets; ii. means for preparing a binary word for each coordinate position of the bit planes, the binary word comprising one bit from each bit plane and the bits of the binary word being ordered in accordance with the assigned bit positions; and iii. means for evaluating said binary words to identify said at least one two-dimensional overlap region.

Claim 38

The apparatus of claim 21, further comprising: e. second controllable positioning means for positioning a focus point within the field of view; and f. means for controlling said second controllable positioning means to successively position the focus point at a plurality of said selected nets of the device within the positioned field of view.

Claim 39

The apparatus of claim 21, further comprising: e. second controllable positioning means for positioning a focus point within the field of view; f. means for identifying a portion of a selected net at which the focus point is to be positioned, such that said portion is spaced apart from neighboring nets of the device by a minimum separation distance; and g. means for controlling said second controllable positioning means to position the focus point at said identified portion of a selected net.

Claim 40

The apparatus of claim 37, wherein said means for identifying a portion of a selected net comprises: i. means for expanding each polygon lying within the field of view to produce a respective expanded polygon; ii. means for identifying regions of overlap of the expanded polygons; iii. means for identifying portions of a selected net which are separated from said regions of overlap of the expanded polygons by a minimum separation distance.

Claim 41

The apparatus of claim 21, wherein said field of view is adjustable to define a field of view of variable dimension, and further comprising means for determining a minimum field of view dimension for which the field of view can be positioned such that the selected nets are within the field of view.